All the data you need.

Tag: Number Theory

Additive functions
A function f from positive integers to real numbers is defined to be additive if for relatively prime numbers m and n, f(mn) = f(m) + f(n). The function f is called completely addititive if the above holds for all positive integers m and n, i.e. we drop the requirement …
Advanced questions about a basic diagram
I saw a hand-drawn version of the diagram above yesterday and noticed that the points were too evenly distributed. That got me to thinking: is there any objective way to say that this famous diagram is in some sense complete? If you were to make a diagram with more points, …
Factoring pseudoprimes
Fermat’s little theorem says that if p is a prime number, then for any positive integer b < p we hve bp-1 = 1 (mod p). This theorem gives a necessary but not sufficient condition for a number to be prime. Fermat’s primality test The converse of Fermat’s little theorem …
Connecting the FFT and quadratic reciprocity
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. …
Factored random numbers
A couple days ago Michael Nielsen posted an image of a one-page paper that gives an algorithm for generating factored random numbers, uniformly distributed from 1 to some designated N. The algorithm does not generate random numbers then factor them. It’s more efficient than that, generating the factorization along with …
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 …