All the data you need.

Tag: Number Theory

When there is only one group of a given size
Today’s date, US style, is 9/26/2023, and there is only one group, up to isomorphism, of size 9262023. You could verify this in Mathematica with the command FiniteGroupCount[9262023] which returns 1. For a given n, when is there only one group of size n? There are two requirements. First, n …
Mersenne primes are unsafe
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 …
Primes, weeds, and military precision
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 …
Gauss map, Euclidean algorithm, and continued fractions
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 …
Elliptic curve addition formulas
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 …
Rational height functions
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 …
Finite field Diffie Hellman primes
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 …
Chinese Remainder Theorem synthesis algorithm
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 …
Gaining efficiency by working modulo factors
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 …
Can the chi squared test detect fake primes?
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. When data fall into a number of buckets, with a moderate number …
Fake primes
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 …
Twin stars and twin primes
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 …
Floors and roots
I recently stumbled across the identity while reading [1]. Here ⌊x⌋ is the floor of x, the largest integer not larger than x. My first thought was that this was hard to believe. Although the floor function is very simple, its interactions with other functions tends to be complicated. I …
Numbers don’t typically have many prime factors
Suppose you select a 100-digit number at random. How many distinct prime factors do you think it would have? The answer is smaller than you might think: most likely between 5 and 6. The function ω(n) returns the number of distinct prime factors of n [1]. A theorem of Hardy …
Leading digits of primes
How are the first digits of primes distributed? Do some digits appear as first digits of primes more often that others? How should we even frame the problem? There are an infinite number of primes that begin with each digit, so the cardinalities of the sets of primes beginning with …
Recognizing three-digit primes
If a three-digit number looks like it might be prime, there’s about a 2 in 3 chance that it is. To be more precise about what it means for a number to “look like a prime,” let’s say that a number is obviously composite if it is divisible by 2, …
Overpowered proof that π is transcendental
There is no polynomial with rational coefficients that evaluates to 0 at π. That is, π is a transcendental number, not an algebraic number. This post will prove this fact as a corollary of a more advanced theorem. There are proof that are more elementary and direct, but the proof …
Piranhas and prime factors
The piranha problem says an event cannot be highly correlated with a large number of independent predictors. If you have a lot of strong predictors, they must predict each other, analogous to having too many piranhas in a small body of water. The piranha problem is subtle. It can sound …