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.

Newton's method is a simple and efficient method for finding the roots of equations, provided you start close enough to the root. But determining the set of starting points that converge to a given root, or converge at all, can be very complicated. In one case it is easy to completely classify where points converge. [...]The post A Continental Divide for Newton's Method first appeared on John D. Cook.

Here's another little chess puzzle by Martin Gardner, taken from this paper. The task is to place all the pieces-king, queen, two bishops, two knights, and two rooks-on a 6 * 5 chessboard, with the requirement that the two bishops be on opposite colored squares and no piece is attacking another. Here is a solution.The post All pieces on a small chessboard first appeared on John D. Cook.

Our team started working within Nvidia in early 2009 at the beginning of the ORNL Titan project. Our Nvidia contacts dealt with applications, libraries, programming environment and performance optimization. First impressions were that their technical stance on issues was very reasonable. One obscure example: in a C++ CUDA kernel were you allowed to use enums," [...]The post Experiences with Nvidia first appeared on John D. Cook.

The previous post mentioned Legendre polynomials. This post will give a brief introduction to these polynomials and a couple hints of how they are used in applications. One way to define the Legendre polynomials is as follows. P0(x) = 1 Pk are orthogonal on [-1, 1]. Pk(1) = 1 for all k >= 0. The [...]The post Legendre polynomials first appeared on John D. Cook.

To first approximation, a satellite orbiting the earth moves in an elliptical orbit. That's what would get from solving the two-body problem: two point masses orbiting their common center of mass, subject to no forces other than their gravitational attraction to each other. But the earth is not a point mass. Neither is a satellite, [...]The post The biggest perturbation of satellite orbits first appeared on John D. Cook.

Suppose you have a radio transmitter T and a receiver R with a clear line of sight between them. Some portion the signal received atR will come straight fromT. But some portion will have bounced off some obstacle, such as the ground. The reflected radio waves will take a longer path than the waves that [...]The post Transmission Obstacles and Ellipsoids first appeared on John D. Cook.

The exponential sum of the day page on my site draws an image every day by plugging the month, day, and year into a formula. Details here. Today's image looks almost solid blue in the middle. The default plotting line width works well for most days. For example, see what the sum of the day [...]The post Zooming in on a fractalish plot first appeared on John D. Cook.

All integers are real numbers, but most computer representations of integers do not equal computer representations of real numbers. To make the statement above precise, we have to be more specific about what we mean by computer integers and floating point numbers. I'll use int32 and int64 to refer to 32-bit and 64-bit signed integers. [...]The post Most ints are not floats first appeared on John D. Cook.

Years ago I wrote about a fast way to test whether an integer n is a square. The algorithm rules out a few numbers that cannot be squares based on their last (hexadecimal) digit. If the the integer passes through this initial screening, the algorithm takes the square root of n as a floating point [...]The post Test whether a large integer is a square first appeared on John D. Cook.

What does an eighteenth century French mathematician have to do with the Ethereum cryptocurrency? A pseudorandom number generator based on Legendre symbols, known as Legendre PRF, has been proposed as part of a zero knowledge proof mechanism to demonstrate proof of custody in Ethereum 2.0. I'll explain what each of these terms mean and include [...]The post Legendre and Ethereum first appeared on John D. Cook.

The previous post looked at a function formed by patching together the function f(x) = log(1 +x) for positivex and f(x) =x for negativex. The functions have a mediocre fit, which may be adequate for some applications, such as plotting data points, but not for others, such as visual design. Here's a plot. There's something [...]The post Patching functions together first appeared on John D. Cook.

I saw a post online this morning that recommended the transformation I could see how this could be very handy. Often you want something like a logarithmic scale, not for the exact properties of the logarithm but because it brings big numbers closer in. And for big values ofx there's little difference between log(x) and [...]The post Log-ish first appeared on John D. Cook.

Suppose you have a system withn possible states. The entropy of the system is maximized when all states are equally likely to occur. The entropy is minimized when one outcome is certain to occur. You can say more. Starting from any set of probabilities, as you move in the direction of more uniformity, you increase [...]The post Uniformity increases entropy first appeared on John D. Cook.

The sinc function sinc(x) = sin(x) /x comes up continually in signal processing. Ifx is moderately small, the approximation sinc(x) (2 + cos(x))/3 is remarkably good, with an error on the order of x4/180. This could be useful in situations where you're working with the sinc function and thex in the denominator is awkward [...]The post Sinc function approximation first appeared on John D. Cook.

Four years ago I wrote a blog post about simple solutions to client problems. The post opens by recounting a conversation with a friend that ended with my friend saying So, basically you're recommending division." That conversation came back to me recently when I had a similar conversation during a deposition. I had to explain [...]The post Arithmetic for fun and profit first appeared on John D. Cook.