John D. Cook

Some readers will look at the title of this post and think Ah yes, the FFT. I use it all the time. But what is this quadratic reciprocity?" Others will look at the same title and think Gauss called the quadratic reciprocity theorem the jewel in the crown of mathematics. But what is this FFT [...]The post Connecting the FFT and quadratic reciprocity first appeared on John D. Cook.

It's common to truncate US zip codes to the first three digits for privacy reasons. Truncating to the first two digits is less common, but occurs in some data sets. HIPAA Safe Harbor requires sparse 3-digit zip codes to be suppressed; even when rolled up to three digits some regions are still sparsely populated. How [...]The post Two-digit zip codes first appeared on John D. Cook.

Bessel functions are to polar coordinates what sines and cosines are to rectangular coordinates. This is why Bessel function often arise in applications with radial symmetry. The locations of the zeros of Bessel functions are important in application, and so you can find software for computing these zeros in mathematical libraries. In days gone by [...]The post Bessel zero spacing first appeared on John D. Cook.

Suppose we have an n * n chessboard. The case n = 8 is of course most common, but we consider all positive integer values of n. The graph of a chess piece has an edge between two squares if and only if the piece can legally move between the two squares. Now suppose we [...]The post Coloring the queen's graph first appeared on John D. Cook.

A SWIFT-BIC number identifies a bank, not a particular bank account. The BIC part stands for Bank Identifier Code. I had to look up the structure of SWIFT-BIC codes recently, and here it is: Four letters to identify the bank Two letters to identify the country Two letters or digits to identify the location Optionally, [...]The post Regex to match SWIFT-BIC codes first appeared on John D. Cook.

I just finished reading The Three Body Problem. At the end of the book is a preview of Cixin Liu's book Supernova Era. A bit of dialog in that preview stood out to me because it is touches on themes I've written about before. I've heard about that. When a butterfly flaps its wings, there's [...]The post Bad takes on chaos theory first appeared on John D. Cook.

The news from Meta last week is a vivid reminder of the importance of making code run faster and more power-efficiently. Meta intends to purchase 350,000 Nvidia H100 GPUs this year [1]. Assuming 350W TDP [2] and $0.1621 per kW-h [3] average US energy cost, one expects a figure of $174 million per year in [...]The post New Ways To Make Code Run Faster first appeared on John D. Cook.

A naive view of simple substitution ciphers is that they are secure because there are 26! ways to permute the English alphabet, and so an attacker would have to try 26! 4 * 1026 permutations. However, such brute force is not required. In practice, simple substitution ciphers are breakable by hand in a few [...]The post Brute force cryptanalysis first appeared on John D. Cook.

Introduction Computers fundamentally changed cryptography, opening up new possibilities for making and breaking codes. At first it may not have been clear which side benefited most, but now it's clear that computers gave more power to code makers than code breakers. We now have cryptographic primitives that cannot be attacked more efficiently than by brute [...]The post Straddling checkerboard encryption first appeared on John D. Cook.

I will soon be discontinuing the email subscription option for this blog. I recommend that email subscribers switch over to subscribing to the RSS feed for the blog. If you're unfamiliar with RSS, here is an article on how to get started. (I recommend RSS in general, and not just for subscribing to this blog. [...]The post Email subscription changes first appeared on John D. Cook.

I was thinking about the work I did when I worked in biostatistics at MD Anderson. This work was practical rather than mathematically elegant, useful in its time but not of long-term interest. However, one result came out of this work that I would call elegant, and that was a symmetry I found. Let X [...]The post Beta inequality symmetries first appeared on John D. Cook.

Given a function f(x,y), how can you tell whetherf can be factored into the product of a function g(x) of x alone and a function h(y) of y alone? Depending on how an expression for f is written, it may or may not be obvious whether f(x, y) can be separated into g(x) h(y). There [...]The post When is a function of two variables separable? first appeared on John D. Cook.

When a nonlinear first order ordinary differential equation has the form with n 1, the change of variables turns the equation into a linear equation in u. The equation is known as Bernoulli's equation, though Leibniz came up with the same technique. Apparently the history is complicated [1]. It's nice that Bernoulli's equation can [...]The post Applications of Bernoulli differential equations first appeared on John D. Cook.

Large language models have recently achieved remarkable test scores on well-known academic and professional exams (see, e.g., [1], p. 6). On such tests, these models are at times said to reach human-level performance. However, there is one test that humans can pass but every AI method known to have been tried has abysmally failed. The [...]The post The IQ Test That AI Can't Pass first appeared on John D. Cook.

I've started a new Twitter account: @CryptographyTip. The icon for the account is the symbol for XOR, a common operation in encryption. I intend to post about cryptography theory as well as practical matters such as software and file formats. You can find a list of my other technical twitter accounts here. You can also [...]The post New Twitter account for cryptography first appeared on John D. Cook.

The geometric, logarithmic, and arithmetic means of a and b are defined as follows. A few days ago I mentioned that G L A. The logarithmic mean slips between the geometric and arithmetic means. Or to put it another way, the logarithmic mean is bounded by the geometric and arithmetic means. You can [...]The post Means of means bounding the logarithmic mean first appeared on John D. Cook.

I've mentioned base 64 encoding a few times here, but I've left out a detail. This post fills in that detail. Base 64 encoding comes up in multiple contexts in which you want to represent binary data in text form. I've mentioned base 64 encoding in the context of Gnu ASCII armor. A more common [...]The post Base 64 encoding remainder problem first appeared on John D. Cook.

Gnu Privacy Guard includes a way to encode binary files as plain ASCII text files, and turn these text files back into binary. This is intended as a way to transmit encrypted data, but it can be used to convert any kind of file from binary to text and back to binary. To illustrate this, [...]The post Binary to text to binary first appeared on John D. Cook.

Why might you see aTM in the middle of an otherwise intelligible file? The reason is very similar to the reason you might see , which I explained in the previous post. You might want to read that post first if you're not familiar with Unicode and character encodings. It all has to do with [...]The post Why a caret, euro, trademark" aTM in a file? first appeared on John D. Cook.

You may have seen a web page with the symbol scattered throughout the text, especially in older web pages. What is this symbol and why does it appear unexpected? The symbol we're discussing is a bit of a paradox. It's the (valid) Unicode character to represent an invalid Unicode character. If you just read [...]The post A valid character to represent an invalid character first appeared on John D. Cook.

Suppose a function f(z) equals 0 at z = 0, 1, 2, 3, .... Under what circumstances might you be able to conclude that f is zero everywhere? Clearly you need some hypothesis on f. For example, the function sin(z) is zero at every integer but certainly not constantly zero. Carlson's theorem says that if [...]The post When zeros at natural numbers implies zero everywhere first appeared on John D. Cook.

Everybody cares about codes running fast on their computers. Hardware improvements over recent decades have made this possible. But how well are we taking advantage of hardware speedups? Consider these two C++ code examples. Assume here n = 10000000. void sub(int* a, int* b) { for (int i=0; i<n; ++i) a[i] = i + [...]The post When High Performance Computing Is Not High Performance first appeared on John D. Cook.

The confusion between numbers such as 7 and 007 comes up everywhere. We know they're different-James Bond isn't Agent 7-and yet the distinction isn't quite trivial. How should software handle the two kinds of numbers? The answer isn't as simple as Do what the user expects" because different users have different expectations. Excel If you [...]The post Leading zeros first appeared on John D. Cook.

Let with each component satisfying 0 < xi 1/2. Define the complement x' by taking the complement of each entry. Let G andA represent the geometric and arithmetic mean respectively. Then Ky Fan's inequality says Now let H be the harmonic mean. Since in general H G A, you might guess that [...]The post Ky Fan's inequality first appeared on John D. Cook.

The Digital Signature Standard (DSS) FIPS 184-4, first published in 2013, expires a few days from now, on February 3, 2024. It is superseded by NIST FIPS 184-5. This new version was published on February 3, 2023, giving everyone a year to adopt the new new standard before it became required. The differences between the [...]The post Previous digital signature standard expires next month first appeared on John D. Cook.

The average of two numbers,a andb, can be written as the average of x over the interval [a, b]. This is easily verified as follows. The average is the arithemtic mean. We can represent other means as above if we generalize the pattern to be For the arithmetic mean, (x) = x. Logarithmic mean If [...]The post Integral representations of means first appeared on John D. Cook.

Let An, Gn and Hn be the arithmetic mean, geometric mean, and harmonic mean of a set of n numbers. When n = 2, the arithmetic mean times the harmonic mean is the geometric mean squared. The proof is simple: When n > 2 we no longer have equality. However, W. Sierpiski, perhaps best known [...]The post Sierpiski's inequality first appeared on John D. Cook.

The Five Safes decision framework was created a couple decades ago by Felix Ritchie at the UK Office for National Statistics. It is a framework for evaluating the safe use of confidential data, particularly by government agencies. You can find a description of the Five Safes, for example, in NIST SP 800-188. The Five Safes [...]The post The Five Safes data privacy framework first appeared on John D. Cook.

The exponential sum page on this site draws a new image every day based on plugging the month, day, and year into a formula. Some of these images are visually appealing; I've had many people ask if they could use the images in publications or on coffee mugs etc. The images generally look very different [...]The post A curious pattern in January exponential sums first appeared on John D. Cook.

The following post is by Wayne Joubert, the newest member of our consulting team. Wayne recently retired from his position as a Senior Computational Scientist at Oak Ridge National Laboratory. Training large language models like GPT-4 costs many millions of dollars in server expenses. These costs are expected to trend to billions of dollars over [...]The post The Million Dollar Matrix Multiply first appeared on John D. Cook.

On New Years Day I posted about groups of order 2024. Are there elliptic curves of order 2024? The Hasse-Weil theorem relates the number of points on an elliptic curve over a finite field to the number of elements of the field. Namely, an elliptic curve E over a field with q elements must have [...]The post Is there an elliptic curve with 2024 points? first appeared on John D. Cook.

I needed the inverse factorial function for my previous post. I was sure I'd written a post on computing the inverse factorial, and intended to reuse the code from that earlier post. But when I searched I couldn't find anything, so I'm posting the code here for my future reference and for anyone else who [...]The post Computing inverse factorial first appeared on John D. Cook.

What factorial is closest to the square root of 2024 factorial? A good guess would be 1012, based on the idea that (n!) might be near (n/2)!. This isn't correct-the actual answer is 1112-but it's not wildly off. Could it be that (2n)! is asymptotically (n!)^2? No, Gauss' duplication formula shows that the ratio of [...]The post Square root factorial first appeared on John D. Cook.

Given an integer n, suppose you want to compute n, the greatest integer less than or equal to the square root of n. One reason you may want to compute n is to know when you can stop trial division when factoring n. Similarly, n gives you a starting point for Fermat's factorization algorithm. With [...]The post Computing square root floor first appeared on John D. Cook.

This time last year I wrote about groups of order 2023 and now I'd like to do the same for 2024. There are three Abelian groups of order 2024, and they're not hard to find. We can factor 2024 = 8 * 11 * 23 and so the Abelian groups of order 2024 are of [...]The post Groups of order 2024 first appeared on John D. Cook.

Two of the first things you learn in cryptography are that simple substitution ciphers are very easy to break, and that security by obscurity is a bad idea. This post will revisit both of these ideas. Security depends on your threat model. If the threat you want to protect against is a human reading your [...]The post Weak encryption and surveillance first appeared on John D. Cook.

Yesterday I wrote about a way to memorize a random 256-bit encryption key. This isn't trivial, but it's doable using memory techniques. There's a much easier way to create a memorable encryption key: start with something memorable, then apply a hash function. Why not just do that? There are two conflicting criteria to satisfy: cryptographic [...]The post Randomize, then humanize first appeared on John D. Cook.

Here is an introduction to manifolds (PDF, 23 MB) unlike any I've seen before. These notes by Brian Beckman devote a substantial amount of time to thinking about the problem of describing a location on a manifold, including an unexpected diversion into What3Words. The notes are in the form of a Mathematica notebook. The link [...]The post An unusual introduction to manifolds first appeared on John D. Cook.

There are techniques that can enable anyone to memorize much more than may seem possible. This post will show how I generated and memorized a 256-bit encryption key this morning using the approach explained here. TANSTAAFL There ain't no such thing as a free lunch. This saying is abbreviated TANSTAAFL in Heinlein's novel The Moon [...]The post Example of memorizing a 256-bit private key first appeared on John D. Cook.

These were the most popular posts I wrote in 2023. Privacy and encryption First names and Bayes' theorem What is the point of a public key fingerprint? RSA encryption in practice Geometry A pentagon, hexagon, and decagon walk into a bar (source of the image above) Calculating the intersection of two circles Number theory Every [...]The post Top twelve posts of 2023 first appeared on John D. Cook.

John Conway's Doomsday" rule observes that that every year, the dates 4/4, 6/6, 8/8, 10/10, 12/12, 5/9, 9/5, 7/11, and 11/7 fall on the same day of the week. In 2024 all these dates fall on a Thursday. These dates are easy to memorize because they break down in double pairs of even digits-4/4, 6/6, [...]The post Doomsday 2024 first appeared on John D. Cook.

The last couple blog posts have been about Dixon elliptic functions, functions which are analogous in some ways to sine and cosine functions. Whereas sine and cosine satisfy a Pythagorean identity the Dixon functions sm and cm satisfy what you might call a Fermat identity alluding to Fermat's last theorem. The functions sm and cm [...]The post Addition theorems for Dixon functions first appeared on John D. Cook.

The Fermat curve of ordern is the set of points satisfying xn + yn = 1 for a positive integer n. Fermat's last theorem is equivalent to saying there are no non-trivial rational points on the Fermat curve of order n > 2. (The trivial points have x or y equal to 0.) Parameterization The [...]The post Fermat curve first appeared on John D. Cook.

The Dixon elliptic functions sm and cm are in some ways analogous to sine and cosine. However, whereas sine and cosine satisfy the Dixon functions satisfy The exponent 3 foreshadows the fact that these functions have a sort of three-fold symmetry. In particular, the function sm maps an equilateral triangle in the complex plane to [...]The post Conformal map between disk and equilateral triangle first appeared on John D. Cook.

As a student, I often made the mistake of thinking that if I knew a more powerful theorem, I didn't need to learn a less powerful theorem. The reason this is a mistake is that the more powerful theorem may be better by one obvious criterion but not be better by other less-obvious criteria. The [...]The post Integrals involving secants and tangents first appeared on John D. Cook.

Public key cryptography uses two keys: a private key and a public key. The nature of these keys depends on the encryption scheme, such as whether one is using RSA, ECC, or some other method, but you can think of a key as a long number. A key may be a short list of numbers, [...]The post What is the point of a public key fingerprint? first appeared on John D. Cook.

The diff utility compares files by lines, which is often what you'd like it to do. But sometimes you'd like more granularity. For example, supposed we want to compare two versions of Psalm 23. Here are the first three verses in the King James version: The Lord is my shepherd; I shall not want. He [...]The post Fine-grained file differences first appeared on John D. Cook.

I stumbled on the book Ed Mastery by Michael W. Lucas and couldn't tell immediately whether it was serious. In a sort of technical version of Poe's law, Lucas lays on the technical machismo pretty thick, but not thicker than some people do unironically. Bravado Here's a paragraph from early in the book. Many younger [...]The post The ed line editor: bravado, utility, and history first appeared on John D. Cook.

A few days ago I wrote about sufficient conditions for f(g(x)) to bound g(f(x)). This evening I stumbled on an analogous theorem. For real numbers and , cos( sin(x)) > sin( cos(x)) for all real x provided ^2 + ^2 < (/2)^2. Source: American Mathematical Monthly. February 2009. Solution to problem 11309, page 184. [...]The post sin(cos(x)) versus cos(sin(x)) first appeared on John D. Cook.

There is a conformal map between any two simply connected open proper subsets of the complex plane. This means, for example, there is a one-to-one analytic map from the interior of a square onto the interior of a a circle. Or from the interior of a triangle onto the interior of a pentagon. Or from [...]The post Rectangles to Rectangles first appeared on John D. Cook.