You can’t hide from the primes

What are primes?

A prime number is a positive integer with exactly two different divisors. For example, 2 is prime, as 1 and 2 divide it. The same is true for 3, 5, and 7. But 6 is not prime as it has four divisors 1, 2, 3 and 6.

Image result for ulam spiral
The Ulam spiral, where colored cells are primes. A larger version is the featured image of the blog.

On first glance, we may think that primes are not so useful. After all, we don’t use primes in daily life. Or do we? Read on!

First, we provide a few basic and not so basic facts about primes.

  • A handy fact: to determine that a number n is prime, check for prime divisors at most √n. For example, we can quickly determine that 83 is prime by checking that 2, 3, 5 and 7 are not divisors.
  • Every number is a product of primes. For example, 26 = 2• 13, and this is called a prime factorization. Prime factorizations are unique up to the order of the factors. This is one of the simplest reasons why primes matter: in a sense, they form an infinite periodic table of elements from which all other numbers are built. If you know a numbers prime factorization, then it tells you something fundamental about that number. Depending on the work you are doing, it may be better to represent 12,397 as 7 2 • 11 • 23.
  • At the time of writing this blog, the largest prime that we know is 274,207,281 − 1, a number with over twenty two million digits. Of course, there are much larger primes. In fact, most primes are larger than this tiny number! As Euclid proved over two thousand years ago, there are infinitely many primes.
  • If you look at how they are dispersed on the number line, then the primes are ubiquitous.  According to the Bertrand–Chebyshev theorem: if you take an integer n and double it to form 2n, then you know there is always a prime between n and 2n.
  • Primes don’t seem to arise according to any fixed pattern that we know. However, long clumps of them do appear in certain kinds of patterns. An arithmetic progression is a sequence of integers of the form an+b. For example, 3, 5, and 7 appear as 2n+3, where n = 0, 1, and 2. A breakthrough result of Ben Green and Terrance Tao from 2004 showed that arbitrarily long, finite sequences of primes are contained in arithmetic progressions.
  • There are fast algorithms to check if a number is prime. Agrawal, Kayal, and Saxena proved in 2002 that deciding if a number is prime or composite is in polynomial time. However, we don’t know the computational complexity of finding the prime factorization of an integer.

Primes also have beautiful density patterns as exhibited by the prime number theorem and the Ulam spiral. Check out this video on the density of primes.

Why are primes important to security?

Primes matter in real life. You can’t hide from the primes. Each time you use your bank card or do on-line shopping, primes are likely lurking in the background.

Image result for melissa mccarthy hiding spicy
As Spicey knows, you can’t hide from the primes.

The science of encoding and transmitting secure data is called cryptography. Cryptography has an ancient past, but in the last century mathematicians developed sophisticated cryptographic algorithms that are very hard to crack.

Cryptography algorithms like RSA and others rely on so-called trapdoor functions; that is, functions easy to compute in one direction but not in the reverse. For example, prime factorization is a trap door: if I give you two primes, then it is easy to compute their product. However, if I give you a large number that is the product of two primes like 2997 -1, then it extremely tough to find the two primes.

Many other applications in computer science and engineering use primes. For example, random number generators and error correcting codes exploit properties of primes.

Why are primes interesting to mathematicians?

To put it bluntly, mathematicians don’t understand primes as well as would like.

Primes are the bread and butter of number theory, and in that field, there are many deep, unsolved problems them. One of the simplest to state of these is the Goldbach conjecture: each even integer greater than 2 is a sum of two primes. For example, 8 is 3+5, and 26 is 23+3.  The Goldbach conjecture has been open since the 18th century.

The 1742 letter from Christian Goldbach to Leonhard Euler posing his namesake conjecture.

We don’t understand gaps between primes very well. The Twin Prime Conjecture states that there infinitely many primes p so that p+2 is also prime. In other words, we can find infinitely many examples of primes with gap 2.  In 2013, Yitang Zhang announced that he could prove there were infinitely many primes with gap less than 70 million. That gap may seem ridiculously large, but it was a major breakthrough. Using his techniques, Terrance Tao and others have reduced the gap down to 246.

Image result for yitang yang math
Yitang Yang, who is the subject of the movie Counting From Infinity.

Another deep unsolved problem connected to primes is the Riemann hypothesis, which is more technical to state. Define the Riemann zeta function (or just zeta function) at value s as the infinite series:\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}

The zeta function can take complex values, and is defined if the real part of s is greater than 1; for example, at s=1 it is the divergent harmonic series. At s=2, it has value π2/6.

There are infinitely many zeroes (that is, solutions of the equation ζ(s)=0) of the zeta function, such as the negative even integers, and these are called trivial zeroes. The zeta function also has complex number zeroes. The Riemann hypothesis claims that the real part of any non-trivial zero of the zeta function is 1/2. In other words, all the non-trivial zeroes live on the critical line z = 1/2 in the complex plane.

RiemannZetaZerosContoursReIm
A visualization of the Riemann zeta function in the complex plane, with the black dots representing zeroes. Notice the zeroes on the critical line z = 1/2.

While the Riemann hypothesis appears unrelated to primes on the surface, many conjectures about primes rely on its validity. One consequence has to do with the distribution of primes numbers. When I recently interviewed Barry Mazur (whose book on primes and the Riemann hypothesis came our recently; Barry is one of the leading number theorists), he gave his perspective on this connection.  We close with his words.
Image result for prime numbers and the Riemann hypothesis

“Draw a graph (on one standard-size page) that charts the number of primes less than x, and where the range is for values of x between 1 and, say, 40, and it looks like the most randomly constructed staircase. And now draw one where the range is for values of x between 1 and, say, 100,000 primes and you get a strikingly smooth graph! Looking at primes from afar, their erratic turbulence disappears. That is the perplexity: from afar the graph of primes is so smooth, while from near it looks disorganized and complicated. The Riemann hypothesis continues the grand project begun by Gauss of explaining exactly how smooth that progression of primes is.”

Anthony Bonato

2 thoughts on “You can’t hide from the primes

  1. This is interesting stuff. Prime numbers have always fascinated me.
    By chance I discovered a way to factorize a number without having to divide anything. It turns out some easily-generated sequences have such a relationship that unless a term from one can be found in the other, then the value of n used to generate one of those sequences must be prime. These sequences need only a number of terms equal to a quarter of n and, thanks to a handy mathematical law it, each term need not have any more than a very low number of digits no matter how large the value of n. This, in essence (I have to be careful, as you well know, what I communicate over the Internet) is how it works. It seems to me it would be very easy for a powerful computer to generate and sort through the two sets of data looking for a match. Much easier than the current method of trying to divide huge numbers into huge numbers. Do you have any thoughts on this?

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s