The Evolution of Algorithms to find Prime Numbers

Abstract

Prime numbers, and the deterministic formulas used to find them, have garnered considerable attention from mathematicians, professionals and amateurs alike. A prime number is a positive integer, excluding 1, whose only divisors are 1 and itself. For example, 23 is a prime number as it can only be divided by 1 and 23. A number that is not prime is called a composite number.

While prime numbers under 100 are fairly abundant, they become less frequent and difficult to find in a systematic manner as the digits in the number increase since they do not appear to follow a predictable distribution. So why do researchers keep studying them? For over 150 years, mathematicians have attempted to uncover a deterministic formula to identify prime numbers. If such a formula existed, all numbers could be factored relatively quickly using computers. Paradoxically, much of electronic data today is encrypted by taking advantage of the fact that it is difficult and time consuming for a computer program to factor a large composite number. A formula to find all prime numbers would be a significant breakthrough in mathematics, but severely detrimental to data security.