John D. Cook

An RSA public key is a pair of numbers (e,n) wheree is an exponent andn =pq wherep andq are large prime numbers. The original RSA paper said choose a private key d and computee. In practice now we choosee and computed. Furthermore, e is now almost always 65537 for reasons given here. So the public [...]The post A quiet change to RSA first appeared on John D. Cook.

Fermat numbers The nth Fermat number is defined by Pierre Fermat conjectured that the F(n) were prime for alln, and they are forn = 0, 1, 2, 3, and 4, but Leonard Euler factoredF(5), showing that it is not prime. Tangent numbers Thenth tangent number is defined by the Taylor series for tangent: Another way [...]The post Fermat primes and tangent numbers first appeared on John D. Cook.

If you need to memorize a list of up to eight words, particularly for a short period of time, the most efficient method may be brute force: rehearse the words in sequence until you can remember them. But if you need to remember more words, or remember the list for a longer time, some sort [...]The post Memorizing a list of seed words first appeared on John D. Cook.

Several years ago I asked myself a couple questions. Which things, if I were 10x better at, would make little difference? Which things, if I were 10% better at, would make a big difference? I remember realizing, in particular, that if I knew 10x more about statistics, it wouldn't make a bit of difference. The [...]The post 10x vs 10% first appeared on John D. Cook.

The optimal choice of factoring algorithm depends on the size of the number you want to factor. For numbers larger than a googol (10100) the GNFS (general number field sieve) algorithm is the fastest known factoring algorithm, making GNFS the algorithm of choice for trying to factor public keys for RSA encryption The expected time [...]The post Time needed to factor large integers first appeared on John D. Cook.

This post will include some simple but useful calculations. Throughout this post, a and b are real numbers greater than 1. All logs are proportional For any two bases a and b, log base a and log base b are proportional, and in fact the proportionality constant is logb a. We have or to put [...]The post log log x first appeared on John D. Cook.

The previous post needed to fit a double exponential function to data, a function of the form By taking logs, we have a function of the form where thea in the latter equation is the log of thea in the former. In the previous post I used a curve fitting function from SciPy to find [...]The post Fitting a double exponential function to three points first appeared on John D. Cook.

In 2001, a quantum computer was able to factor 15. In 2012, a quantum computer was able to factor 21, sorta. They cheated by not implementing gates that they knew a priori would not be used. To this day, there still hasn't been a quantum computer to factor 21 without taking some shortcuts. Some reasons [...]The post Extrapolating quantum factoring first appeared on John D. Cook.

If and when practical scalable quantum computers become available, RSA encryption would be broken, at least for key sizes currently in use. A quantum computer could use Shor's algorithm factor n-bit numbers in time on the order of n^2. The phrase quantum leap" is misused and overused, but this would legitimately be a quantum leap. [...]The post Post-quantum RSA with gargantuan keys first appeared on John D. Cook.

John Conway discovered a right triangle that can be partitioned into five similar triangles. The sides are in proportion 1 : 2 : 5. You can make a larger similar triangle by making the entire triangle the central (green) triangle of a new triangle. Here's the same image with the small triangles filled in as [...]The post Conway's pinwheel tiling first appeared on John D. Cook.

Bitcoin transactions appear to be private because names are not attached to accounts. But that is not sufficient to ensure privacy; if it were, much of my work in data privacy would be unnecessary. It's quite possible to identify people in data that does not contain any direct identifiers. I hesitate to use the term [...]The post Silent Payments first appeared on John D. Cook.

In elementary algebra we learn how to solve ax2 + bx + c = 0 for roots r = r1, r2. But how about the inverse problem: given a real-valued r, find integer coefficients a, b and c such that r is a root of the corresponding quadratic equation. A simple approximation can be found [...]The post An inverse problem for the quadratic equation first appeared on John D. Cook.

The previous post looked at solving the equation which arises from the Mollweide map projection. Newton's method works well unless is near /2. Using a modified version of Newton's method makes the convergence faster when = /2, which is kinda useless because we know the solution is $theta; = /2 there. When [...]The post Inverting series that are flat at zero first appeared on John D. Cook.

Karl Brandan Mollweide (1774-1825) designed an equal-area map projection, mapping the surface of the earth to an ellipse with an aspect ratio of 2:1. If you were looking at the earth from a distance, the face you're looking at would correspond to a circle in the middle of the Mollweide map [1]. The part of [...]The post Mollweide map projection and Newton's method first appeared on John D. Cook.

There are four manmade object that have left our solar system: Pioneer 10, Pioneer 11, Voyager 1, and Voyager 2. Yesterday I wrote about the Golden Record which is on both of the Voyager probes. Some of the graphics on the cover of the Golden Record is also on plaques attached to the Pioneer probes. [...]The post 1420 MHz first appeared on John D. Cook.

If AI can do part of your job, you're likely to either be fired or promoted. AI will always have some error rate, and if it can do your job at an acceptable error rate, you'll need to find another job. But if the error rate is not acceptable, the ability to identify and fix [...]The post The AI fork in the road first appeared on John D. Cook.

Yesterday I wrote a post outlining mental math posts I'd written over the years. I don't write about mental math that often, but I've been writing for a long time, and so the posts add up. In the process of writing the outline post I noticed a small gap. In the post on mentally calculating [...]The post Day of the week centuries from now first appeared on John D. Cook.

Suppose you're learning a new language and want to boost your vocabulary in a very time-efficient way. People have many ways to learn a language, different for each person. Suppose you wanted to improve your vocabulary by reading books in that language. To get the most impact, you'd like to pick books that cover as [...]The post Learning languages with the help of algorithms first appeared on John D. Cook.

I've written quite a few posts on mental math over the years. I think mental math is important/interesting for a couple reasons. First, there is some utility in being able to carry out small calculations with rough accuracy without having stop and open up a calculator. Second, the constraints imposed by mental calculation make you [...]The post Mental math posts first appeared on John D. Cook.

The two Voyager probes, launched in 1977, are now in interstellar space beyond our solar system. Each carries a Golden Record, a recording of sounds and encoded images meant to represent Earth and human civilization. I've long intended to listen to the record and yesterday I did. One of the cuts is a 12-minute collage [...]The post Morse code beyond the solar system first appeared on John D. Cook.

Last week I wrote about a mental random number generator designed by George Marsaglia. It's terrible compared to any software RNG, but it produces better output than most people would if asked to say a list of random digits. Marsaglia's RNG starts with a two-digit number as a seed state, then at each step replacesn [...]The post Cycles in Marsaglia's mental RNG first appeared on John D. Cook.

I wrote a couple posts last month about the seed phrase words used by Bitcoin and other cryptocurrencies. There are 2048 words on theBIP39 list. Monero uses a different word list, one with 1626 words [1]. You can find Monero's list here. Why 1626 words? It's not hard to guess why the BIP 39 list [...]The post Monero's seed phrase words first appeared on John D. Cook.

Let f(z) = (az + b)/(cz + d) where = ad - bc 1. Iff has no singularity inside the unit disk, i.e. if |d/c| > 1, then the image of the unit disk under f is another disk. What is the area of that disk? The calculation is complicated, but the result [...]The post Area of the unit disk after a Mobius transformation first appeared on John D. Cook.

Yesterday I wrote about a triangle inequality discovered by Paul Erds. LetPbe a point inside a triangleABC. Letx,y,zbe the distances fromPto the vertices and letp,q,r, be the distances to the sides. Then Erds' inequality says x+y+z>= 2(p+q+r). Using the same notation, here are four more triangle inequalities discovered by Oppenheim [1]. px + qy + [...]The post More triangle inequalities first appeared on John D. Cook.

LetD be the unit disk in the complex plane and letf be a univalent function on D, meaning it is analytic and one-to-one on D. There is a simple way to compute the area off(D) from the coefficients in its power series. If then The first equality follows from the change of variables theorem for [...]The post Area of unit disk under a univalent function first appeared on John D. Cook.

Ted Dunning left a comment on my post on random sampling from a triangle saying you could extend this to sampling from a polygon by dividing the polygon into triangles, and selecting a triangle each time with probability proportional to the triangle's area. To illustrate this, let's start with a irregular pentagon. To pick a [...]The post Random samples from a polygon first appeared on John D. Cook.

Plane geometry has been studied since ancient times, and yet new results keep being discovered millennia later, including elegant results. It's easy to come up with a new result by proving a complicated theorem that Euclid would not have cared about. It's more impressive to come up with a new theorem that Euclid would have [...]The post A triangle inequality by Erds first appeared on John D. Cook.

If you have a triangle with verticesA,B, andC, how would you generate random points inside the triangleABC? Barycentric coordinates One idea would be to use barycentric coordinates. Generate random numbers , , and from the interval [0, 1]. Normalize the points to have sum 1 by dividing each by their sum. Return A + [...]The post Randomly selecting points inside a triangle first appeared on John D. Cook.

George Marsaglia was a big name in random number generation. I've referred to his work multiple times here, most recently in this article from March on randomly generating points on a sphere. He is best remembered for his DIEHARD battery of tests for RNG quality. See, for example, this post. I recently learned about a [...]The post A mental random number generator first appeared on John D. Cook.

Unicode 17.0 was released yesterday. According to the announcement This version adds 4,803 new characters, including four new scripts, eight new emoji characters, as well as many other characters and symbols, bringing the total of encoded characters to 159,801. My primary interest in Unicode is for symbols. Here are some of the new symbols I [...]The post New symbols in Unicode 17 first appeared on John D. Cook.

The Mandelbrot set is the set of complex numbers csuch that iterations of f(z) =z^2 +c remain bounded. But how do you know an iteration will remain bounded? You know when it becomes unbounded-if |z| > 2 then the point isn't coming back-but how do you know whether an iteration will never become unbounded? You [...]The post Mandelbrot and Fat Tails first appeared on John D. Cook.

Bech32 is an algorithm for encoding binary data, specifically Bitcoin addresses, in a human-friendly way using a 32-character alphabet. The Bech32 alphabet includes lowercase letters and digits, removing the digit 1, and the letters b, i, and o. The Bech32 alphabet design is similar to that for other coding schemes in that it seeks to [...]The post Bech32 encoding first appeared on John D. Cook.

The previous post reported that a study found a 95% confidence interval for the the area of the Mandelbrot set to be 1.506484 0.000004. What was the sample size that was used to come to that conclusion? A 95% confidence interval for a proportion is given by and so if a confidence interval of [...]The post Inferring sample size from confidence interval first appeared on John D. Cook.

The two latest posts have been about the Mandelbrot set, the set ofcomplex numbers csuch that iterations of f(z) =z^2 +c remain bounded. It's easy to see that the sequence of iterates will go off to infinity if at any step |z| > 2. For eachc, we can look at the escape time, the number [...]The post Mandelbrot area and escape times first appeared on John D. Cook.

As mentioned in the previous post, most of the area in the Mandelbrot set comes from two regions. The largest is the blue cardioid region below and the next largest is the orange disk. The blue cardioid is the set of pointsc such that iterations of z^2 + c converge to a fixed point. The [...]The post Mandelbrot points of every period first appeared on John D. Cook.

The Mandelbrot set is one of the most famous fractals. It consists of the complex numbers c such that iterations of f(z) = z^2 + c are bounded. The plot of the Mandelbrot set is a complicated image-it's a fractal, after all-and yet there's a simple description of an first approximation to the Mandelbrot set. [...]The post Minimalist Mandelbrot set first appeared on John D. Cook.

I was listening to a podcast with Bill Buchanan recently in which he demonstrated the difficulty of various cryptographic tasks by the amount of energy they would use and how much water that would boil. Some tasks would require enough energy to boil a teaspoon of water, some a swimming pool, and some all the [...]The post Measuring cryptographic strength in liters of boiling water first appeared on John D. Cook.

A rational triangle is a triangle whose sides have rational length and whose area is rational. Can any two rational numbers be sizes of a rational triangle? Surprisingly no. You can always find a third side of rational length, but it might not be possible to do so while keeping the area rational. The following [...]The post Impossible rational triangles first appeared on John D. Cook.

The most important mathematical function after the basics is the gamma function. If I could add one function to a calculator that has trig functions, log, and exponential, it would be the gamma function. Or maybe the log of the gamma function; it's often more useful than the gamma function itself because it doesn't overflow [...]The post Trigamma first appeared on John D. Cook.

Bitcoin addresses are essentially hash values of public keys encoded in Base58. More details here. The addresses are essentially random characters chosen from the Base58 alphabet: uppercase and lowercase Latin letters and digits, with 0 (zero), I (capital I), O (capital O), and l (lowercase l) removed to prevent errors. You could create an address [...]The post Vanity addresses first appeared on John D. Cook.

Gauss proved in 1818 that the value of integral is unchanged ifx andy are replaced by (x +y)/2 and (xy), i.e. if you replacedx andy with their arithmetic mean and geometric mean [1]. So, for example, if you wanted to compute you could instead compute Notice that the coefficients of sin^2 and cos^2 [...]The post An integral theorem of Gauss first appeared on John D. Cook.

The treasury of El Salvador owns over 6,000 Bitcoins. Its total holdings are currently worth roughly $700,000,000. These coins had been associated with one private key. Yesterday El Salvador announced that it would split its funds into 14 wallets in order to protect the funds from quantum computing. You can confirm using a blockchain explorer [...]The post El Salvador's Bitcoin and Quantum Computing first appeared on John D. Cook.

Bitcoin relies on two kinds of cryptography: digital signatures and hash functions. Quantum computing would be devastating to the former, but not the latter. To be more specific, the kind of digital signatures used in Bitcoin could in theory be broken by quantum computer using Shor's algorithm. Digital signatures could use quantum-resistant algorithms [1], but [...]The post How quantum computing would affect Bitcoin first appeared on John D. Cook.

This post will connect a couple posts from yesterday and explore storing data in images. Connections There's a connection between two blog posts that I wrote yesterday that I only realized today. The first post was about the probability of sending money to a wrong Bitcoin address by mistyping. Checksums make it extremely unlikely that [...]The post Storing data in images first appeared on John D. Cook.

I've written several times about knight's tours of a chessboard. The paths in these tours cross each other many times. What if you wanted to look tours that do not cross themselves? You can't reach every square this way. You can reach half of them, but no more than half. The following tour is part [...]The post An uncrossed knight's tour first appeared on John D. Cook.

I saw a post by Dave Richeson on Mastodon about making QR codes that look like images. Turns out you can shrink a black square in a QR code by up to a factor of three while keeping the code usable. This gives you the wiggle room to create dithered images. I tried a few [...]The post Dithered QR codes first appeared on John D. Cook.

I heard someone say that Bitcoin is dangerous because you could easily make a typo when entering an address, sending money to the wrong person, and have no recourse. There are dangers associated with Bitcoin, such as losing a private key, but address typos are not a major concern. Checksums There are several kinds of [...]The post Probability of typing a wrong Bitcoin address first appeared on John D. Cook.

Explosive datacenter demand has caused developers to leave no stone unturned in search of higher efficiencies. The DeepSeek team, not satisfied with Nvidia's CUDA libraries, used a virtualized form of assembly language (PTX) to write kernel codes to accelerate their AI computations. Others have attempted to generate optimized kernels using AI, though some results have [...]The post Why are CUDA kernels hard to optimize? first appeared on John D. Cook.

The biggest math symbol that I can think of is the Riemann P-symbol The symbol is also known as the Papperitz symbol because Erwin Papperitz invented the symbol for expressing solutions to Bernard Riemann's differential equation. Before writing out Riemann's differential equation, we note that the equation has regular singular points at a,b, andc. In [...]The post The biggest math symbol first appeared on John D. Cook.

The beta distribution is a conjugate prior for a binomial likelihood function, so it makes posterior probability calculations trivial: you simply add your data to the distribution parameters. If you start with a beta(, ) prior distribution on a proportion , then observes successes and f failures, the posterior distribution on is beta( + [...]The post You can't have everything you want: beta edition first appeared on John D. Cook.