John D. Cook

I recently ran across an article by Katherine Stange [1] on Lehmer's factoring stencils [2]. These stencils were the basis of an effective method for factoring moderately large numbers before the advent of electronic computers. This post will describe the stencils and simulate their use with a Python script. Misconceptions When I started reading [1] [...]The post Factoring Stencils first appeared on John D. Cook.

As mentioned in the previous post, crypto wallets often turn a list of words, known as a seed phrase, into private keys. These words come from a list of 211 = 2048 words chosen to be distinct and memorable. You can find the list here. Typically a seed phrase will contain 12 words. For example: [...]The post Recovering a permuted seed phrase first appeared on John D. Cook.

What's in your Bitcoin wallet? Very little. I don't mean very little value, but very little data. If you're a Bitcoin billiionaire, your wallet still doesn't contain very many bits. You might reasonably expect that a crypto wallet is a container, given the analogy with an ordinary wallet, but it's not much of a container. [...]The post What's in your wallet? first appeared on John D. Cook.

Here's a simple way to generate a fractal known as the Twin Dragon. Start with random values of x andy and repeatedly update the according to the rule xnew = (- xold + yold)/2 - b ynew = (- xold - yold)/2 where b is randomly chosen to be 0 or 1 with equal probability. [...]The post Randomly generated dragon first appeared on John D. Cook.

In the process of writing the previous post, I wanted to confirm that the number in the post really is prime. This was useful in debugging my manual conversion of the image to text: errors did not result in a prime number. For example, I didn't see the 9's in the image at first, and [...]The post Converting very long strings to integers in Python first appeared on John D. Cook.

The following prime number looks like a black-and-white image of an American flag. The number mostly consists of the digits 1, 3, and 8, but there are a few 9's. The following image colors the 8's blue, the 3's red, and the 1's white. The background is gray so you can see the 1s. I [...]The post American Flag Prime first appeared on John D. Cook.

I've typed Karl Weierstrass' name quite a few times lately and thought about how you'll sometimes see his name written as Weierstra in English text. That led me to look up the rules for when to use and when to use ss. The rules are moderately complicated, and have varied over time and location. [...]The post Uppercase Eszett first appeared on John D. Cook.

All elliptic curves can be written in Weierstrass form y^2 = x^3 + ax + b with a few exceptions [1]. Montgomery elliptic curves have the form B y^2 =x^3 + A x^2 + x and twisted Edwards curves have the form a x^2 + y^2 = 1 +dx^2 y^2 Every Montgomery curve has a [...]The post Weierstrass, Montgomery, and Edwards elliptic curve forms first appeared on John D. Cook.

A few days ago I wrote about the Jubjub elliptic curve that takes its name from Lewis Carroll's poem Jabberwocky. I've also written about a slightly smaller but still enormous curve named Baby Jubjub. This post introduces Tiny Jubjub, an elliptic curve with 20 elements, one designed to have some properties in common with its [...]The post Tiny Jubjub first appeared on John D. Cook.

The constant is the ratio of a circle's circumference to its diameter. We can generalize by generalizing what a circle is. We will define a p-circle to be the solution to for 1 p . The case ofp = is defined as the limit of the cases ofp asp [...]The post Two ways of generalizing first appeared on John D. Cook.

The elliptic curves used in cryptography are over finite fields. They're not curves" at all in the colloquial sense of the word. But they are defined by analogy with continuous curves, and so most discussions of elliptic curves in cryptography start by showing a plot of a real elliptic curve. Here's a plot of y^2 [...]The post Misleading plots of elliptic curves first appeared on John D. Cook.

The other day I needed to test some software with a moderately large prime number as input. The first thing that came to mind was 8675309. This would not be a memorable number except it was in the chorus of the song 867-5309/Jenny. It turned out that 8675309 was too large. The software would take [...]The post Memorable Primes first appeared on John D. Cook.

This came out a few weeks ago, but I just learned about it today and I think it's hilarious. Duncan Haldane posted on X a screenshot of Google Gemini having a meltdown. I quit. I am clearly not capable of solving this problem. The code is cursed, the test is cursed, and I am a [...]The post Self-loathing AI first appeared on John D. Cook.

At one time Bayesian statistics was not just a minority approach, it was considered controversial or fringe. When I was in grad school, someone confided in me that he was a closet Bayesian. He thought the Bayesian approach to statistics made sense, but didn't want to jeopardize his career by saying so publicly. Then somewhere [...]The post The Rise and Fall of Bayesian Statistics first appeared on John D. Cook.

The Federalist Papers, a collection of 85 essays published anonymously between 1787 and 1788, were one of the first subjects for natural language processing aided by a computer. Because the papers were anonymous, people were naturally curious who wrote each of the essays. Early on it was determined that the authors were Alexander Hamilton, James [...]The post Analyzing the Federalist Papers first appeared on John D. Cook.

Suppose you have an elliptic curve y^2 = x^3 + ax + b over a finite field Fpfor prime p. How many points are on the curve? Brute force You can count the number of points on the curve by brute force, as I did here. Loop through each of thep possibilities forx and fory [...]The post Counting points on an elliptic curve first appeared on John D. Cook.

TF-IDF (Term Frequency-Inverse Document Frequency) is commonly used in natural language processing to extract important words. The idea behind the statistic is that a word is important if it occurs frequently in a particular document but not frequently in the corpus of documents the document came from. The term-frequency (TF) of a word in a [...]The post Using TF-IDF to pick out important words first appeared on John D. Cook.

The White House put out a position paper Strengthening American Leadership in Digital Financial Technology a few days ago. The last page of the paper contains a hex dump. Kinda surprising to see something like that coming out of the White House, but it makes sense in the context of cryptocurrency. Presumably Donald Trump has [...]The post Genesis Block Easter Egg first appeared on John D. Cook.

We often want to reduce something that's inherently two-dimensional into something one-dimensional. We want to turn graph into a list. And we'd like to do this with some kind of faithfulness. We'd like things that are close together in 2D space to be close together in their 1D representation, and vice versa, to the extent [...]The post Making the two-dimensional one-dimensional first appeared on John D. Cook.

Public key cryptography came to the world's attention via Martin Gardner's Scientific American article from August 1977 on RSA encryption. The article's opening paragraph illustrates what a different world 1977 was in regard to computation and communication. ... in a few decades ... the transfer of information will probably be much faster and much cheaper [...]The post Looking back at Martin Gardner's RSA article first appeared on John D. Cook.

Earlier today I wrote about factoring four 255-bit numbers that I needed for a post. Just out of curiosity, I wanted to see how long it would take to factor RSA 100, the smallest of the factoring challenges posed by RSA Laboratories in 1991. This is a 100-digit (330-bit) number that is the product of [...]The post Factoring RSA100 first appeared on John D. Cook.

A couple days ago I wrote about two pair of closely related elliptic curves: Tweedledum and Tweedledee, and Pallas and Vesta. In each pair, the order of one curve is the order of the base field of the other curve. The curves in each pair are used together in cryptography, but they don't form a [...]The post Pairing-unfriendly curves first appeared on John D. Cook.

This post will look at the time required to factor n - 1 each of the following prime numbers in Python (SymPy) and Mathematica. The next post will explain why I wanted to factor these numbers. p = 2254 + 4707489544292117082687961190295928833 q = 2254 + 4707489545178046908921067385359695873 r = 2254 + 45560315531419706090280762371685220353 s = 2254 + [...]The post Time to factor big integers Python and Mathematica first appeared on John D. Cook.

The previous post gave two examples of pairs of elliptic curves in which #(E /Fp) = q and #(E /Fq) = p. That is, the curve E, when defined over integers mod p has q elements, and when defined over the integers mod q has p elements. Pairs Silverman and Stange [1] call this arrangement [...]The post Cycles of Elliptic Curves first appeared on John D. Cook.

Yesterday's post mentioned Tweedledum and Tweedledee, a pair of elliptic curves named after characters in Lewis Carroll's Through the Looking Glass. Zcash uses a very similar pair of elliptic curves for zero-knowledge proofs: Pallas and Vesta. One named after a Greek goddess associated with war, and one named after a Roman goddess associated with home [...]The post Pallas, Vesta, and Zcash first appeared on John D. Cook.

Elliptic curves are often used in cryptography, and in particular they are used in zero-knowledge proofs (ZKP). Cryptocurrencies such as Zcash use ZKP to protect the privacy of users. Several of the elliptic curves used in ZKP have whimsical names taken from characters by Lewis Carroll. This post will look at these five elliptic curves: [...]The post Lewis Carroll and Zero Knowledge Proofs first appeared on John D. Cook.

Iconjack posted on X today (Possibly) surprising fact: a regular dodecahedron is rounder than a regular icosahedron. You might reasonably suppose that having more sides would result in a rounder figure, so a figure with 20 sides should be rounder than a figure with 12 sides. But it's the other way around. Discrete curvature Here's [...]The post Roundest regular solid first appeared on John D. Cook.

Define B = {0, 1} and a Boolean function fp: BN B where p is a Boolean parameter vector in Bn. Consider that fp(x) can be represented as a Boolean expression whose variables are the entries of vectors p and x. Assume that c is the cost of computing fp(x) measured in some way, [...]The post Machine learning by satisfiability solving first appeared on John D. Cook.

If three circles are all tangent to each other, you can find two more circles that are tangent to all three, and the equation for finding these new circles is remarkably elegant. This is Descartes' theorem. Two tangent circles To illustrate Descartes' theorem, we first need three mutually tangent circles. Drawing two mutually tangent circles [...]The post Finding tangent circles first appeared on John D. Cook.

A Pythagorean triangle is a right triangle with integer sides. Aprimitive Pythagorean triangle is one in which the sides have no factor in common. For example a triangle with sides (30, 40, 50) is a Pythagorean triangle but not a primitive Pythagorean triangle. It is possible for two primitive Pythagorean triangles to have the same [...]The post Primitive Pythagorean triangles with the same area first appeared on John D. Cook.

The previous post began by saying Bitcoin's Wallet Import Format (WIF) is essentially Base58 encoding with a checksum." More specifically, WIF uses Base58Check encoding. This post will fill in the missing details and show how to carry out computing Base58Check in Python. There are multiple ways to stub your toe doing this because it involves [...]The post Base58Check encoding in Python first appeared on John D. Cook.

Bitcoin's Wallet Import Format (WIF) is essentially Base58 encoding with a checksum. (See the next post for details.) It is meant to a human-friendly way to display cryptographic private keys. It's not that friendly, but it could be worse. The checksum (the first four bytes of SHA256 applied twice) is appended before the conversion to [...]The post Most legible font for WIF first appeared on John D. Cook.

In the process of writing the previous post, I ran across the Landau-Ramanujan theorem. It turned out to not be what I needed, but it's an interesting result. What portion of the numbers less thanN can be written as the sum of the squares of two non-negative integers? Edmund Landau discovered in 1908, and Srinivasa [...]The post Counting sums of squares first appeared on John D. Cook.

What are the solutions to the equation uxx + uyy = u on the unit square with the requirement that u(x, y) = 0 on the boundary? It's easy to see that the functions u(x, y) = sin(mx) sin(ny) are solutions with = (m^2 + n^2)^2 for non-negative integersm andn. It's not so obvious [...]The post Eigenvalues of the Laplacian on a square first appeared on John D. Cook.

The vibration of a thin membrane is often modeled by the PDE u + u = 0 whereu is the height of the membrane and is the Laplacian. Solutions only exist for certain values of , the eigenvalues of . You could think of u as giving the height of a vibrating drum head [...]The post The sound of drums that tile the plane first appeared on John D. Cook.

The sum of the firstn odd numbers isn^2. For example, 1 + 3 + 5 + 7 + 9 = 25 = 5^2 Here's another way to say the same thing. Start with the list of positive integers, remove every second integer from the list, and take the cumulative sum. The resulting list is the [...]The post Moessner's Magic first appeared on John D. Cook.

The elliptic curves Curve25519 and Ed25519 are both commonly used in applications. For example, Curve25519 is used in Proton Mail and Ed25519 is used in SSH. The two curves are related, as the numerical parts in their names suggest. The two curves are equivalent in some sense that we will describe below. An algebraic geometer [...]The post Equivalence between commonly used elliptic curves first appeared on John D. Cook.

Digital signatures often use elliptic curves. For example, Bitcoin and Ethereum use the elliptic curve secp256k1 [1]. This post will discuss the elliptic curve Ed25519 [2] using in Monero and in many other applications. Ed25519 has the equation y^2 - x^2 = 1 +dx^2 y^2 over the finite field Fq where q = 2255 - [...]The post Monero's elliptic curve first appeared on John D. Cook.

Bitcoin addresses include a checksum. The Base58Check algorithm uses the first four bytes of a hash function as a checksum before applying Base58 encoding. Ethereum addresses did not include a checksum, but it became apparent later that a checksum was needed. How can you retroactively fit a checksum into an address without breaking backward compatibility? [...]The post Retrofitting error detection first appeared on John D. Cook.

When I wrote about hyperinflation the other day I included an image of a 100 trillion dollar note from Zimbabwe. This is almost a cliche: everyone using this image when talking about hyperinflation. But Zimbabwe's 1014 dollar note was not the largest denomination ever used. In 1946, Hungary circulated at 100 quintillion (1020) peng note. [...]The post A bank note with 21 implicit zeros first appeared on John D. Cook.

A few days ago I wrote about now hyperinflation changes everything. I'd like to follow up with another example of hyperinflation breaking implicit assumptions. Something I was reading this week gave the approximation for present value v = 1/(1 + i) 1 - i + i^2 This implicitly assumes that the interest rate i [...]The post Taylor Series and the Argentine Peso first appeared on John D. Cook.

There are several numbers that are analogous to binomial coefficients and, at least in Donald Knuth's notation, are written in a style analogous to binomial coefficients. And just as binomial coefficients can be arranged into Pascal's triangle, these numbers can be arranged into similar triangles. In Pascal's triangle, each entry is the sum of the [...]The post Analogs of binomial coefficients first appeared on John D. Cook.

Actuarial mathematics makes frequent use of a notation that as far as I know isn't used anywhere else, and that is a bracket enclosing the northeast corner of a symbol. This is used as subscript of another symbol, such as ana or ans, and there may be other decorations such more superscripts or subscripts. For [...]The post Annuity and factorial notation first appeared on John D. Cook.

Base58 encoding and Base85 encoding are used to represent binary data in a human-friendly way. Base58 uses a smaller character set and so is more conservative. Base85 uses a larger character set and so is more efficient. There is a gotcha in that base" means something different in Base58 compared to Base85. More on that [...]The post Base58 versus Base85 encoding first appeared on John D. Cook.

My two latest blog posts have been about compound interest. I gave examples of interest rates of 6% up to 18% per year. Hyperinflation, with rates of inflation in excess of 50% per month, changes everything. Although many economists accept 50% per month as the threshold of hyperinflation, the world has seen worse. Zimbabwe, for [...]The post Hyperinflation changes everything first appeared on John D. Cook.

The previous post looked at the difference between continuously compounded interest and interest compounded a large discrete number of times. This difference was calculated using the following Python function. def f(P, n, r) : return P*(exp(r) - (1 + r/n)**n) where the function arguments are principle, number of compoundings, and interest rate. When I was [...]The post Numerical problem with an interest calculation first appeared on John D. Cook.

When I was a child, I heard an advertisement for a bank that compounded the interest on your savings account with every heartbeat. I thought that was an odd thing to say and wondered what it meant. If you have a rapid heart rate, does your money compound more frequently? I figured there was probably [...]The post Interest compounding with every heartbeat first appeared on John D. Cook.

Yesterday's post looked at the distribution of powers ofx mod 1. For almost allx > 1 the distribution is uniform in the limit. But there are exceptions, and the post raised the question of whether 3 + 2 is an exception. A plot made itlook like 3 + 2 is an exception, but that turned [...]The post Powers of 3 + 2 first appeared on John D. Cook.

For a positive real numberx, the expressionx mod 1 means the fractional part ofx: x mod 1 =x - x . This post will look at the distributions ofnx mod 1 and xn mod 1 for n = 1, 2, 3, .... The distribution of nx mod 1 is easy to classify. Ifx is [...]The post Multiples and powers mod 1 first appeared on John D. Cook.

AI models hallucinate, and always will [1]. In some sense this is nothing new: everything has an error rate. But what is new is the nature of AI errors. The output of an AI is plausible by construction [2], and so errors can look reasonable even when they're wrong. For example, if you ask for [...]The post Evaluating and lowering AI hallucination cost first appeared on John D. Cook.