John D. Cook

A couple days ago I wrote about Donald Knuth's expression for the twindragon fractal as a sum of powers ofb = 1 -i. Simone Conradi made a nice animation replacing (1 -i) with exp(2it) (1 - i). The animation loops over values oft. Here's what you get whent = 0.3. And here's what you get [...]The post Variations on Knuth's Twindragon first appeared on John D. Cook.

Pick's theorem is a surprising and useful to find the area of a region formed by connecting dots on a grid. The area is simply A = i +p/2 - 1 wherei is the number of dots in the interior andp is the number of dots on the perimeter. Example For example, the in the [...]The post Intuition for Pick's Theorem first appeared on John D. Cook.

A few days ago I wrote about a random process that creates a fractal known as the Twin Dragon. This post gives a deterministic approach to create the same figure. As far as I can tell, the first reference to this fractal is in a paper by Davis and Knuth in the Journal of Recreational [...]The post Knuth's Twindragon first appeared on John D. Cook.

A few days ago I wrote about what's in a crypto wallet. In that post I said that most crypto wallets now are hierarchical deterministic (HD) wallets. And I said that HD wallets are deterministic in the sense that they derive all their keys from a seed phrase. But in what sense are HD wallets [...]The post What's hierarchical about a hierarchical wallet? first appeared on John D. Cook.

Today I learned that the size and shape of a punch card was chosen to be the same as US paper money at the time. At the time a US bank note had dimensions 3.25'' by 7.375''. This was sometime prior to 1929 [1] when the size of a bank note changed to 2.61'' by [...]The post Punch Cards and Dollar Bills first appeared on John D. Cook.

Last week I gave an example of a randomly generated fractal and mentioned that it was a particularly special case of a more general algorithm for generating similar fractals found in [1]." Here's the general pattern. First, create a non-singular matrixM with integer entries and let k be the determinant ofM. LetP be the parallelogram [...]The post A recipe for creating random fractals first appeared on John D. Cook.

I was skimming through a book [1] the other day and saw the following three equations: log 1.3712885742 = 0.13712885742 log 237.5812087593 = 2.375812087593 log 3550.2601815865 = 3.5502601815865 The sequence of digits is the same on both sides of each equation, except for the position of the decimal point. The book said The determination of [...]The post When log(x) has the same digits as x first appeared on John D. Cook.

Today's exponential sum, like all the exponential sums on the site, is formed by drawing a line between consecutive partial sums of a series involving complex exponentials. The exponential sum page makes an image each day by putting the day's month, day, and year into a formula. Here's today's image based on the sum I [...]The post Connecting partial sums first appeared on John D. Cook.

A couple days ago I wrote about how you might go about trying to recover a seed phrase that you had remembered out of order. I said that the list of seed phrase words had been designed to be distinct. Just out of curiosity I computed how similar the words are using Levenshtein distance, also [...]The post A lot of seed phrase words are similar first appeared on 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.