What makes prime numbers so special

Multiplying two numbers, even if very large, is perhaps tedious but a straightforward task. Finding prime factorisation, on the other hand, is extremely hard, and that is precisely what the RSA system takes advantage of.

Suppose that Alice and Bob wish to communicate secretly over the internet. They require an encryption system. If they first meet in person, they can devise a method for encryption and decryption that only they will know, but if the initial communication is online, they need to first openly communicate the encryption system itself — a risky business. However, if Alice chooses two large prime numbers, computes their product, and communicates this openly, finding out what her original prime numbers were will be a very difficult task, as only she knows the factors.

So Alice communicates her product to Bob, keeping her factors secret. Bob uses the product to encrypt his message to Alice, which can only be decrypted using the factors that she knows. If Eve tries to break the product down into its prime factors — even using the fastest supercomputer — no known algorithm exists that can accomplish that before the sun will explode.

Large prime numbers are used prominently in other cryptosystems too. The faster computers get, the larger the numbers they can crack. But is it possible to state an accurate theorem that will express exactly how rare they are? Such a theorem was first stated as a conjecture by the great mathematician Carl Friedrich Gauss in , at the age of The nineteenth-century mathematician Bernhard Riemann Figure 1 , who influenced the study of prime numbers in modern times more than anyone else, developed further tools needed to deal with it.

But a formal proof of the theorem was given only in , a century after it had been stated. It is interesting to note that both men were born around the time of the death of Riemann.

The precise formulation of the prime number theorem, even more so the details of its proof, require advanced mathematics that we cannot discuss here. But put less precisely, the prime number theorem states that the frequency of prime numbers around x is inversely proportional to the number of digits in x.

Indeed, computer calculations show that there are 75 prime numbers in the first window, 49 in the second and only 37 in the third, between one trillion and one trillion plus one thousand. The same information can be pictured as a graph, shown below Figure 3. Notice that any time we meet a new prime along the x -axis, the graph rises by 1, so the graph takes the shape of steps Figure 3A.

On a small scale, it is hard to detect a pattern in the graph. It is quite easy to prove that we can find arbitrarily large intervals in which there are no prime numbers, meaning spans where the graph does not rise.

On a larger scale, however, the graph looks smooth Figure 3B. This smooth curve seen on a large scale demonstrates the prime number theorem. Systems in probability, such as coin flipping, behave in this way. It is impossible to predict the result of a single coin flipping, but over time, if the coin is unbiased, it will come up heads half the time. What is surprising is that the prime number system is not probabilistic, but it still behaves in many ways as if it were randomly selected.

Number theory, which includes the study of prime numbers, is rich with unsolved problems, unsuccessfully tackled by the greatest minds for hundreds of years. A few of those open problems are mathematical statements that have not been proven yet, but in whose correctness, we strongly believe. If you manage to prove any of them, you will win eternal fame. If you were not intrigued so far, maybe this prize will motivate you….

Why is this important? Who does it interest? Mathematicians judge their problems first and foremost by their difficulty and intrinsic beauty. Prime numbers score high in both of these criteria. However, prime numbers are also useful in a practical way. Research on prime numbers has found an important use in encryption the science of encoding secret messages in the past few decades.

We mentioned earlier the fictional book by Carl Sagan, on an extraterrestrial culture communicating with mankind using prime numbers. Like many other codes for encryption, the one found on almost every debit card, called RSA named after its inventors—Rivest, Shamir, and Adleman , is based on the properties of prime numbers. The story of prime numbers is still surrounded with mystery.

So, their story is not yet over and done with…. The proof is based on basic assumptions that were tested, or on other theorems that were previously proven. There are mathematical conjectures over which people still disagree. We're going to call it P. So then I'll take all the prime numbers up to P and multiply them all together. If I do that and add one to the product, that number has to be a prime.

If a number is a composite, in contrast, it's always divisible by some quantity of lower prime numbers. So why have primes held such fascination among mathematicians for thousands of years? As Zegarelli explains, a lot of higher mathematics is based upon primes. But there's also cryptography, in which primes have a critical importance, because really large numbers possess a particularly valuable characteristic. There's no quick, easy way to tell if they're prime or composite, he says.

The difficulty of discerning between huge primes and huge composites makes it possible for a cryptographer to come up with huge composite numbers that are factors of two really big primes, composed of hundreds of digits.

If I've got one of those factors in my pocket, I've got the key to the house. That's why mathematicians have continued to labor to come up with increasingly bigger primes, in an ongoing project called the Great Internet Mersenne Prime Search. In , that project led to the discovery of a prime number that consisted of 23,, digits, enough to fill 9, book pages, as University of Portsmouth England mathematician Ittay Weiss described it in The Conversation.

It took 14 years of computations to come up with the gigantic prime, which is more than , times bigger than the estimated number of atoms in the observable universe! In computers began to be used to calculate even larger new prime numbers.

That year a new record was set with a digit number, but this number began to grow rapidly with advances in computing. The great leap from thousands to millions of digits came about mainly because of one person. The current record is held by the 51 st known Mersenne prime. This real colossus, M , discovered on December 7, by Florida programmer Patrick Laroche, reaches the unimaginable length of 24,, digits ; if someone were to try to print it on paper, almost 10, sheets would be needed.

And the search goes on. Our progress is dependent on the number of users and advancements in hardware. But leaving aside the economic incentive or the headlines, what motivates this search? For mathematicians, the importance of prime numbers is indisputable; since the rest of the natural numbers are broken down into a product of primes , they are considered building blocks in number theory. However, despite the theoretical purity defended by mathematicians, the truth is that prime numbers have also brought great practical benefits to humanity, such as electronic commerce.

In , three researchers designed RSA cryptography using the initials of Rivest, Shamir and Adleman , based on the known product of two large prime numbers, which can only be deciphered by those who know the factors.

This type of encryption, called asymmetric or public key , is used for encryption on the Internet, for example in digital signatures, and is the most important current application of large prime numbers.

However, only numbers with a few hundred digits are used; it would be unthinkable to use the giant primes known today. So, do these numerical giants have any specific uses?