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.

The Major mnemonic system is a method of converting numbers to words that can be more easily memorized. The basics of the system can be written on an index card, but there are practical details that are seldom written down. Presentations of the Major system can be misleading, intentionally or unintentionally, by implying that it [...]The post Memorizing four-digit numbers first appeared on John D. Cook.

Let A be an n * n complex matrix. The numerical range of A is the image of x*Ax over the unit sphere. That is, the numerical range of A is the set W(A) in defined by W(A) = {x*Ax | x n and ||x|| = 1} where x* is the conjugate transpose of [...]The post The numerical range ellipse first appeared on John D. Cook.

Ben Grimmer posted something yesterday on Twitter: A nice mathematical puzzle If you take a 4-norm ball and cut it carefully, you will find a two-norm ball. 3D printed visual evidence below. The puzzle: Why does this happen and how much more generally does it happen? (This question was first posed to me by Pablo [...]The post Random slices of a sphube first appeared on John D. Cook.

Are there more twin stars or twin primes? If the twin prime conjecture is true, there are an infinite number of twin primes, and that would settle the question. We don't know whether there are infinitely many twin primes, and it's a little challenging to find any results on how many twin primes we're sure [...]The post Twin stars and twin primes first appeared on John D. Cook.

Evenly placing points on a sphere is a difficult problem. It's impossible in general, and so you distribute the points as evenly as you can. The results vary according to how you measure how evenly the points are spread. However, there is a fast and simple way to distribute points that may be good enough, [...]The post Simple way to distribute points on a sphere first appeared on John D. Cook.

If you've only seen one definition of spherical coordinates, you may be shocked to discover that there are multiple conventions. In particular, mathematicians and geoscientists have different conventions. As Volker Michel put it in book on constructive approximation, Many mathematicians have faced weird jigsaw puzzles with misplaced continents after using a data set from a [...]The post Spherical coordinate Rosetta Stone first appeared on John D. Cook.

A Traveling Salesman tour visits a list of destinations using the shortest path. There's an obvious way to find the shortest path connecting N points: try all N! paths and see which one is shortest. Unfortunately, that might take a while. Texas has 254 counties, and so calculating a tour of Texas counties by brute [...]The post Creating a Traveling Salesman Tour of Texas with Mathematica first appeared on John D. Cook.

A spherical cap is the portion of a sphere above some horizontal plane. For example, the polar ice cap of the earth is the region above some latitude. I mentioned in this post that the area above a latitude is where R is the earth's radius. Latitude is the angle up from the equator. [...]The post Area and volume of hypersphere cap first appeared on John D. Cook.

In high dimensions, randomly chosen vectors are very likely nearly orthogonal. I'll unpack this a little bit then demonstrate it by simulation. Then I'll look at what happens when we restrict our attention to points with positive coordinates. *** The lengths of vectors don't contribute to the angles between them, so we may as well [...]The post Random points in a high-dimensional orthant first appeared on John D. Cook.

The previous post looked at cosine similarity for embeddings of words in vector spaces. Word embeddings like word2vec map words into high-dimensional vector spaces in such a way that related words correspond to vectors that are roughly parallel. Ideally the more similar the words, the smaller the angle between their corresponding vectors. The cosine similarity [...]The post Cosine similarity does not satisfy the triangle inequality first appeared on John D. Cook.

Natural language processing represents words as high-dimensional vectors, on the order of 100 dimensions. For example, the glove-wiki-gigaword-50 set of word vectors contains 50-dimensional vectors, and the the glove-wiki-gigaword-200 set of word vectors contains 200-dimensional vectors. The intent is to represent words in such a way that the angle between vectors is related to similarity [...]The post Angles between words first appeared on John D. Cook.

This post will discuss two scripting languages, but that's not what the post is really about. It's really about expressiveness and (or versus) productivity. *** I was excited to discover the awk programming language sometime in college because I had not used a scripting language before. Compared to C, awk was high-level luxury. Then a [...]The post Productive constraints first appeared on John D. Cook.

A Mobius transformation is a function of the form where ad - bc = 1. We usually think of z as a complex number, but it doesn't have to be. We could define Mobius transformations in any context where we can multiply, add, and divide, i.e. over any field. In particular, we could work over [...]The post Mobius transformations over a finite field first appeared on John D. Cook.