John D. Cook

Simple groups are the building blocks of groups similar to the way prime numbers are the building blocks of integers. This post will unpack this analogy in two ways: How do simple groups compare to prime numbers? How does the composition of simple groups compare to the composition of prime numbers? The former analogy is [...]The post Analogy between prime numbers and simple groups first appeared on John D. Cook.

The word normal" in mathematical nomenclature does not always means usual" or customary" as it does in colloquial English. Instead, it might that something has a convenient property. That is the case for normal subgroups. We can do things with normal subgroups that we cannot do with other subgroups, such as take quotients, and so [...]The post Normal and non-normal subgroups first appeared on John D. Cook.

In the previous post I mentioned that a particular Mersenne prime would be unsuitable for cryptography. In fact, all Mersenne primes are unsuitable for cryptography. A prime number p is called safe" if p = 2q + 1 where q is also a prime. Safe primes are called safe because p - 1 does not [...]The post Mersenne primes are unsafe first appeared on John D. Cook.

Electronic computers were invented before public key cryptography. Would public key cryptography have been possible before computers? The security of RSA encryption depends on the ratio of the difficulty of factoring relative to the difficulty of multiplication. This ratio was high, maybe higher, before modern computers. Suppose the idea of RSA encryption had occurred to [...]The post Victorian public key cryptography first appeared on John D. Cook.

I like generating long LaTeX documents from org-mode because, for one thing, org-mode has nice section folding. But not everyone I work with uses Emacs, so its better to work in LaTeX directly rather than have Emacs generate LaTeX. AUCTeX has section folding for LaTeX documents, though so far I've only has limited success at [...]The post Navigating a LaTeX file first appeared on John D. Cook.

It's surprisingly hard to find a complete list of HTML entities in the form of a data file. There are numerous sites that give lists, often incomplete, in a page formatted to be human-readable but not machine-readable. Here's an XML file from the W3C. Here's a two-column text file I created from the W3C data.The post HTML entity data first appeared on John D. Cook.

I've needed to use double-struck capital letters lately, also called blackboard bold. There are a few quirks in how they are represented in Unicode and in HTML entities, so I'm leaving some notes for myself here and for anyone else who might need to look this up. Unicode The double-struck capital letters are split into [...]The post Double-struck capital letters first appeared on John D. Cook.

Here's a quote from Don Zagier that I found in Larry Rolen's lecture notes on modular forms. There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role [...]The post Primes, weeds, and military precision first appeared on John D. Cook.

A continued fraction of the form with n terms can be written as the composition where As discussed in the previous post, a Mobius transformation can be associated with a matrix. And the composition of Mobius transformations is associated with the product of corresponding matrices. So the continued fraction at the top of the post [...]The post Continued fractions as matrix products first appeared on John D. Cook.

A function of the form where ad - bc 0 is sometimes called a fractional linear transformation or a bilinear transformation. I usually use the name Mobius transformation. In what sense are Mobius transformations linear transformations? They're nonlinear functions unless b = c = 0. And yet they're analogous to linear transformations. For starters, [...]The post Fractional linear and linear first appeared on John D. Cook.

The Awk programming language was named after the initials of its creators. In the preface to a book that just came out, The AWK Programing Language, Second Edition, the authors give a little background on this. Naming a language after its creators shows a certain paucity of imagination. In our defense, we didn't have a [...]The post Naming Awk first appeared on John D. Cook.

Warm up The geometric mean of two numbers is the square root of their product. For example, the geometric mean of 9 and 25 is 15. More generally, the geometric mean of a set of n numbers is the nth root of their product. Alternatively, the geometric mean of a set of n numbers the [...]The post Geometric mean on unit circle first appeared on John D. Cook.

The Gauss map [1] is the function where y is the floor of y, the greatest integer no larger than y. I've written about this map a couple times before. First, I wrote about how this map is measure-preserving. Second, I wrote about the image at the top of the post, based on Michael Trott's [...]The post Gauss map, Euclidean algorithm, and continued fractions first appeared on John D. Cook.

The goal of this post is to unpack a remark in [1]: ... we can say this in fancier terms. Fix a field k .... We say that an elliptic curve E defined over k is that functor which ... Well that is fancy. But what does it mean? Looking for objects A functor is [...]The post An elliptic curve is a functor first appeared on John D. Cook.

The geometric description of addition of points P and Q on an elliptic curve involves four logical branches: If one of P or Q is the point at infinity ... Else if P = Q ... Else if P and Q lie on a vertical line ... Else ... It would seem that an algorithm [...]The post Elliptic curve addition formulas first appeared on John D. Cook.

Mathematicians often speak informally about the relative simplicity of rational numbers. For example, musical intervals that correspond to simple fractions have less tension than intervals that correspond to more complicated fractions. Such informal statements can be made more precise using height functions. There are a variety of height functions designed for different applications, but the [...]The post Rational height functions first appeared on John D. Cook.

If you ask someone a question and they say yes" immediately, that gives you different information than if they pause and slowly say yes." The information you receive is not just the response but also the time it took to generate the response. Encryption can be analogous. The time it takes to encrypt data can [...]The post Timing attacks first appeared on John D. Cook.

I concluded the previous post by saying elliptic curve Diffie-Hellman key exchange (ECDHE) requires smaller keys than finite field Diffie-Hellman (FFDHE) to obtain the same level of security. How much smaller are we talking about? According to NIST recommendations, a 256-bit elliptic curve curve provides about the same security as working over a 3072-bit finite [...]The post Elliptic curve Diffie-Hellman key exchange first appeared on John D. Cook.

Diffie-Hellman key exchange is conceptually simple. Alice and Bob want to generate a shared cryptographic key. They want to use asymmetric (public) cryptography to share a symmetric (private) key. The starting point is a large prime p and a generator 1 < g < p. Alice generates a large random number x, her private key, [...]The post Finite field Diffie Hellman primes first appeared on John D. Cook.

Suppose m = pq where p and q are large, distinct primes. In the previous post we said that calculations mod m can often be carried out more efficiently by working mod p and mod q, then combining the results to get back to a result mod m. The Chinese Remainder Theorem assures us that [...]The post Chinese Remainder Theorem synthesis algorithm first appeared on John D. Cook.

Suppose m is a large integer that you are able to factor. To keep things simple, suppose m = pq where p and q are distinct primes; everything in this post generalizes easily to the case of m having more than two factors. You can carry out calculations mod m more efficiently by carrying out [...]The post Gaining efficiency by working modulo factors first appeared on John D. Cook.

RSA encryption a map from numbers mod n to numbers mod n where n is a public key. A message is represented as an integer m and is encrypted by computing c = me mod n where e is part of the public key. In practice, e is usually 65537 though it does not have [...]The post Group theory and RSA encryption first appeared on John D. Cook.

Not all messages encrypted with the RSA algorithm can be decrypted. This post will show why this is possible and why it does not matter in practice. RSA in a nutshell RSA encryption starts by finding two large primes, p and q. These primes are kept secret, but their productn = pq is made public. [...]The post RSA encrypted messages that cannot be decrypted first appeared on John D. Cook.

Dimension 2 The equation for the perimeter of an ellipse is wherea is the semimajor axis, e is eccentricity, and E is a special function. The equation is simple, in the sense that it has few terms, but it is not elementary, because it depends on an advanced function, the complete elliptic integral of the [...]The post Hyperellipsoid surface area first appeared on John D. Cook.

I posted some notes this morning on how to find the perimeter of an ellipse given its axes. The notes include a simple approximation, a better but more complicated approximation, and the exact value. So given the semi axes a and b, the notes give three ways to compute the perimeter p. If you are [...]The post Solve for ellipse axes given perimeter first appeared on John D. Cook.

The home team lost in a new way yesterday. The Baltimore Ravens beat the Houston Texans by 25-9. This was the first time that score has been seen in the NFL. Possible individual team scores How many scores are possible? It is possible to score any number of points except 1. You can score 2 [...]The post Possible and actual football scores first appeared on John D. Cook.

Earlier I wrote a post showing what happens when you start with an equilateral triangle, then repeatedly subdivide it into smaller and smaller triangles by drawing lines from the centroid (barycenter) to each of the vertices. I mentioned in that post that I moved the code for finding the center to its own function because [...]The post How you define center matters a lot first appeared on John D. Cook.

I just saw a tweet from Dave Richeson saying I remember as a kid calculating the size difference (diameter) of a belt between each hole. Now I think about it every time I wear a belt. Holes 1 inch apart change the diameter by about one-third of an inch (1/). [Assuming people have a circular [...]The post Belt around an elliptical waist first appeared on John D. Cook.

The other day I saw where Cliff Pickover tweeted some images of triangles recursively subdivided by adding a point to the barycenter of each triangle. The images were not what I expected, so I wanted to reproduce the images to look into this further. Here are the first three steps: I set the alpha value [...]The post Recursive triangle subdivision first appeared on John D. Cook.

One of the most common things a statistician is asked to do is compute a sample. There are well known formulas for this, so why isn't calculating a sample size trivial? As with most things in statistics, plugging numbers into a formula is not the hard part. The hard part is deciding what numbers to [...]The post Justifiable sample size first appeared on John D. Cook.

A large class of checksum algorithms have the following pattern: Think of the bits in a file as the coefficients in a polynomial P(x). Divide P(x) by a fixed polynomial Q(x) mod 2 and keep the remainder. Report the remainder as a sequence of bits. In practice there's a little more to the algorithm than [...]The post Checksum polynomials first appeared on John D. Cook.

Given a square complex matrix A, the Jordan normal form of A is a matrix J such that and J has a particular form. The eigenvalues of A are along the diagonal of J, and the elements above the diagonal are 0s or 1s. There's a particular pattern to the 1s, giving the matrix J [...]The post Jordan normal form: 1's above or below diagonal? first appeared on John D. Cook.

When is the discrete Fourier transform of a vector proportional to the original vector? And when that happens, what is the proportionality constant? In more formal language, what can we say about the eigenvectors and eigenvalues of the DFT matrix? Setup I mentioned in the previous post that Mathematica's default convention for defining the DFT [...]The post Eigenvectors of the DFT matrix first appeared on John D. Cook.

Just as there are multiple conventions for defining the Fourier transform, there are multiple conventions for defining the discrete Fourier transform (DFT), better known as the fast Fourier transform (FFT). [1] This post will look at two DFT conventions, one used in Python's NumPy library, and one used in Mathematica. There are more conventions in [...]The post DFT conventions: NumPy vs Mathematica first appeared on John D. Cook.

Math books often use some illustration from the book contents as cover art. When they do, there's often some mystery to the cover art, and a sense of accomplishment when you get far enough into the book to understand the significance of the cover. (See examples here.) William L. Briggs and Van Emden Henson wrote [...]The post DFT mandalas first appeared on John D. Cook.

In his book How to Read Literature Like a Professor, Thomas Foster says that if a poem looks like a square on the printed page, it's likely a sonnet. The miracle of the sonnet, you see, is that it is fourteen lines long and written almost always in iambic pentameter. ... suffice it to say [...]The post Sonnets are square first appeared on John D. Cook.

Suppose you've been monitoring a rare event for a long time, then you see your first occurrence on the Nth observation. Now what would you say about the event's probability? For example, suppose you're wondering whether dogs ever have two tails. You observe thousands of dogs and never see two tails. But then you see [...]The post First time seeing a rare event first appeared on John D. Cook.

Imagine the following dialog. Logarithms are usually taken to integer bases, like 2 or 10." What about e?" OK, that's an example of an irrational base, but it's the only one." Decibels are logarithms tobase 101/10." Really?!" Yeah, you can read about this here." That's weird. But logarithms are always take to bases bigger than [...]The post Stellar magnitude first appeared on John D. Cook.

US telephone area codes are allocated somewhat randomly. There was a deliberate effort to keep geographical proximity from corresponding to numerical proximity, unlike zip codes. (More of zip code proximity here.) In particular, consecutive area codes should belong to different states. The thought was that this would reduce errors. It's still mostly the case that [...]The post Area codes first appeared on John D. Cook.

I was flipping through Gravitation [1] this weekend and was curious about an illustration on page 309. This post reproduces that graph. The graph is centered at Cairo, Egypt and includes triangles whose side lengths are the distances between cities. The triangles are calculated using only distances, not by measuring angles per se. The geometry [...]The post Curvature at Cairo first appeared on John D. Cook.

Given the equations for two circles, how can you tell whether they intersect? And if they do intersect, how do you find the point(s) of intersection? MathWorld gives a derivation, but I'd like to add the derivation there in two ways. First, I'd like to be more explicit about the number of solutions. Second, I'd [...]The post Calculating the intersection of two circles first appeared on John D. Cook.

Paul Graham said Programming languages teach you not to want what they don't provide." He meant that as a negative: programmers using less expressive languages don't know what they're missing. But you could also take that as a positive: using a simple language can teach you that you don't need features you thought you needed. [...]The post A small programming language first appeared on John D. Cook.

Many numerical integration formulas over a finite interval have the form That is, the integral on the left can be approximated by evaluating the integrand f at particular nodes and taking the weighted sum, and the error is some multiple of a derivative of f evaluated at a point in the interval [a, b]. This [...]The post Quadrature rules and an impossibility theorem first appeared on John D. Cook.

In his book The World Beyond Your Head Matthew Crawford talks about jigs literally and metaphorically. A jig in carpentry is something to hold parts in place, such as aligning boards that need to be cut to the same length. Crawford uses the term more generally to describe labor-saving (or more importantly, thought-saving) techniques in [...]The post Jigs first appeared on John D. Cook.

This morning I wrote about Dan Piponi's fake prime function. This evening I thought about it again and wondered whether the chi-squared test could tell the difference between the distribution of digits in real primes and fake primes. If the distributions were obviously different, this would be apparent from looking at histograms. When distributions are [...]The post Can the chi squared test detect fake primes? first appeared on John D. Cook.

I have an account on Mastodon: johndcook@mathstodon.xyz. Note that's @math... and not @mast... One advantage to Mastodon is that you can browse content there without logging, while Twitter is becoming more of a walled garden. You can browse my account, for example, by going to the URL https://mathstodon.xyz/@johndcook There's hardly any content there at this [...]The post Mastodon account first appeared on John D. Cook.

Someone asked on Math Overflow about the distribution of digits in primes. It seems 0 is the least common digit and 1 the most common digit. Dan Piponi replies this is probably just a combination of general properties of sets of numbers with a density similar to the primes and the fact that primes end [...]The post Fake primes first appeared on John D. Cook.

I've been thinking about things that were ruined by doing about 5% more than was necessary, like an actor whose plastic surgery looks plastic. Sometimes excellence requires pushing ourselves to do more than we want to do or more than we think we can do. But sometimes excellence requires restraint. Context is everything. A few [...]The post Do 5% less first appeared on John D. Cook.

Suppose you are in an air traffic control tower observing a plane moving in a straight line and you want to rotate your frame of reference to align with the plane. In the new frame the plane is moving along a coordinate axis with no component of motion in the other directions. You could do [...]The post Tracking and the Euler rotation theorem first appeared on John D. Cook.

NLP software infers parts of speech by context. For example, the SpaCy NLP software can determine the parts of speech in the poem Jabberwocky even though the words are nonsense. More on this here. If you want to tell the parts of speech for isolated words, maybe software like SpaCy isn't the right tool. You [...]The post Using WordNet to create a PAO system first appeared on John D. Cook.