Prime Pursuits

Ivars Peterson

HUNTING FOR BIG PRIMES

Success in the search for mammoth primes, which hide among composite numbers, requires a lot of patience, luck, and fortitude and takes some strategic planning using a few tools from number theory. The quarry are huge numbers such as 2 ^44,497 - 1. The question is whether this 13,395-digit mammoth, just one of an endless supply of candidates, is prime or composite.

Of course, big-prime hunters could stalk their game simply by writing out the number N and dividing into it, one by one, all the integers, starting with 2. If no integers divide into the target number evenly, N must be a prime. Going any further than the square root of N during the search is pointless because factors are always found in pairs. If N has a factor larger than the square root of N , then the factor's partner must be smaller. Using only odd numbers after division by 2 is another possible shortcut.

In the case of mammoth primes, however, the trial-division method proves to be hopelessly time-consuming. A computer able to carry out a billion trial divisions every second would take considerably longer than the current age of the universe to finish the job. Trial division works best for relatively small numbers, although even a 100-digit number is beyond reach unless it happens to have a small factor or a special structure.

The real trouble with trial division is that it provides more information than is required by the question of whether a number is prime. The method not only supplies the answer but also gives the factors of any number that happens to be composite. The idea, then, is to find techniques that pinpoint primality without at the same time finding factors. If a given number has no small factors, such techniques for testing primality are bound to be speedier than trial division and its variants.

In the seventeenth century, Pierre de Fermat provided the basis for primality-testing methods that don't depend on factoring. Today's faster algorithms are all descendants of what is now usually called Fermat's little theorem. One version of the theorem states that if p is a prime number and b any whole number, then b^P - b is a multiple of p . For example, if p = 7 and b =2, the theorem correctly predicts that 7 divides evenly into 2⁷ - 2, or 126.

The theorem makes it possible to state properties of numbers that are too large even to be written out in decimal form. Knowing that 2 ^44,497- 1 is a prime number (established in 1979), allows us to say that an unimaginably gigantic number such as ₃(2 ^44,497- 1⁾ -3 is evenly divisible by 2 ^44,497- 1. No physically conceivable computer could ever handle such an enormous number, but mathematicians can still deduce some of its properties. Fermat's little theorem can easily be transformed into a test for prime numbers. If p is a prime number and b is any whole number, then the remainder when b^P - b is calculated and divided by p will be zero. Thus, for p 11 and b = 2, 2¹¹ - 2 = 2,048 - 2 = 2,046, and 2,046 divided by 11 has a remainder of zero. This works for all prime numbers. If the remainder is not zero, then the number is composite. The difficulty, however, is that some composite numbers also give a remainder of zero. These composites are called pseudoprime numbers. The number 2 ³⁴¹ - 2, for instance, is a multiple of 341, even though 341 is a composite, being the product of 11 and 31.

Although calculating the value of 2 (or some other number) to a high power seems more formidable than trial division, mathematical shortcuts are possible because only the remainder is of interest. Here, modular arithmetic enters the picture, by making it relatively straightforward to find the remainder when, for example, 3^1,037 - 3 is divided by 1,037. There's no need to calculate the value of 3^1,037 itself. It turns out that 3^1,037 is congruent to (or gives the same remainder as) 845(mod 1,037), and 3^1,037 - 3 is congruent to 842(mod 1,037). Therefore, the remainder on division by 1,037 can't be zero. The number 1,037 is composite. This quick test provides practically no clues about the factors of the number.

All that we need to turn the basic Fermat method into an efficient primality test is a way to weed out the pseudoprimes. Fortunately, pseudoprimes are rare, although for a given value of b, there are an infinite number of them. Below 10¹⁰, for example, there are 455,052,512 primes, but for b = 2, only 14,884 pseudoprimes exist over the same range of whole numbers. The composite number 561 is the smallest pseudoprime for all choices of b.

Because the basic Fermat test does an excellent job, mathematicians and computer scientists have sought to generalize Fermat's test to exclude fake primes. The idea is to do some additional tests to find out more about the composite number that may be masquerading as a prime number. Such tests not only would say "pass" or "fail" but also would provide extra information about the numbers being tested. Moreover, the tests should work on numbers that don't necessarily have a special form.

The results of the tests on a particular number resemble a mosaic, with information about the number caught up in its fragments. If we look at a sufficiently large piece of the mosaic, we get enough information to decide whether a number is a prime or a composite. Like a hologram, the nature of the number being tested can be found in any section of the mosaic, which helps cut down the amount of computer time needed to run this type of primality-testing algorithm. Usually, the tests provide information to conclude that any divisor of the target number must be among a very small set of numbers. If none of the divisors works, the number is a prime.

An especially efficient form of such an algorithm for testing any number for primality was developed in the early 1980s. Len Adleman, Robert Rumely, and Carl Pomerance all contributed toward the invention of the testing algorithm. Rendrik Lenstra then discovered several variations of the new method, which made the procedure easier to run on a computer. Lenstra and Henri Cohen twisted the algorithm into shape to make it more compatible with real computer applications. Tests of their elegant implementation show that arbitrary, 100-digit numbers can be checked in seconds. Previously used algorithms would probably have taken in excess of a 100 years to do the same job.

A crucial question in computer science concerns how much such an algorithm for primality testing can be speeded up. The framework for answering such questions lies in the theory of computational complexity, which classifies some computational problems as "easy and others as "hard," depending on how much time a computer may take to work out a given problem in the worst possible case. Let's illustrate that classification scheme by considering methods for testing the primality of any number with n digits. If the number of computational steps grows at a rate of kn^a, where a and k are fixed and determined by the algorithm characteristics, then primality testing can be done in "polynomial time" and is considered "easy." In other words, if the time required for a computer to solve a problem shows polynomial growth according to, say, the cube of the number's length, then increasing the number of digits from 20 to 50 increases computing time from, perhaps, 1 second to 16 seconds. But if the number of steps grows at a rate of kaⁿ, then the problem is "hard": it can't be decided in polynomial time and needs "exponential time." An algorithm that performs exponentially, at, say, 3ⁿ can turn a 1-second solution into a thousand-century nightmare with a modest increase in the number of digits. It's like the difference between racing along at a steadily increasing pace versus running at a rate that climbs higher and higher as the speed increases.

The new primality-testing method requires exponential time, but the exponent changes so slowly that for reasonably sized numbers, the algorithm behaves a lot like one that operates in polynomial time. The question of whether a polynomial-time algorithm will ever be found for primality testing is still open; so is the question of whether factoring is inherently a "hard" problem. Mathematicians and computer scientists tend to assume that primality testing is easy and factoring hard, but to date, neither assumption has been proved.

The determined pursuit of primes can sometimes lead into novel territory. Primality testing turns out to be incredibly easy if the hunter doesn't mind making a mistake once in a long while, a result that is good enough for many practical applications but not for mathematical proof.

The approach of allowing a tiny chance of error stems from the stunning discovery that playing the odds can be far more efficient than following a preset algorithm. Making a sequence of random guesses yields the right answer most of the time, and the longer you keep up the guessing, the better your chances of ending up with a certified prime. This guessing game hinges on the existence of some numerical property that composites usually possess and that primes never have. Suppose, for instance, that for a composite number n, at least three-quarters of the numbers between 1 and n have a particular property that can be checked very quickly. The test simply consists of picking, say, 50 numbers and checking for the appropriate feature. If any have it, then n can't be a prime. If all trial numbers pass the test, then n is almost certainly a prime. In that case, the chance of n being composite would be at most (1/4)⁵⁰, or 10^-30. If those odds aren't good enough, then trying another 50 numbers takes only seconds, and the chance of error becomes even tinier. Algorithms that depend on such random procedures provide confident guesses rather than firm answers about whether a large integer is prime. They represent a trade-off between greater speed and increased uncertainty.

Value of p for which 2p - 1 is prime	2p - 1	When Proved Prime	Machine Used
2	3
3	7	Antiquity
5	31
7	127
13	8,191	1461
17	131,071	1588
19	524,287
31	2,147,483,647	1772
61	19 digits	1883
89	27 digits	1911
107	33 digits	1914
127	39 digits	1876-1914
521	157 digits
607	183 digits
1,279	386 digits	1952	SWAC
2,203	664 digits
2,281	687 digits
3,217	969 digits	1957	BESK
4,253	1,281 digits	1961	IBM-7090
4,423	1,332 digits
9,689	2,917 digits
9,941	2,993 digits	1963	ILLIAC-II
11,213	3,376 digits
19,937	6,002 digits	1971	IBM 360/91
21,701	6,533 digits	1978	CDC-CYBER- 174
23,209	6,987 digits	1979	CDC-CYBER- 174
44,497	13,395 digits	1979	CRAY-1
86,243	25,962 digits	1983	CRAY-1
132,049	39,751 digits	1983	CRAY X-MP
216,091	65,050 digits	1985	CRAY X-MP/24
FIGURE 2.4 Since 1952, computers have taken over in the search for Mersenne primes. In 1988, Walter Colquitt and Luther Welsh, using an NEC SX-2 supercomputer, discovered the thirty-first Mersenne prime, for which p = 110,503.

Primality testing is also easy when the numbers involved have a special form. The largest known primes are found among Mersenne numbers, named for Marin Mersenne, the French abbot who studied them during the early part of the seventeenth century. Mersenne primes are as hard to miss as gaily striped circus elephants gamboling in an open field. They have difficulty hiding among the composites because their special structure allows the use of relatively simple tests to determine their primality.

A Mersenne number, M_p has the form 2^p - 1, where p is a prime. If M_p itself is a prime, then it is called a Mersenne prime. For example, M₇ = 2⁷ - 1 = 127, which happens to be a prime. In 1644, Mersenne found that M_p is a prime for p=2,3,5,7, 13, 17,and 19. M_p is not prime for 11: M₁₁ = 2¹¹ - 1 = 2,047 = 23 x 89. Based on the trends that he saw, Mersenne predicted that M_p would be prime for p = 31, 67, 127, and 257, and he conjectured that no other such primes occur in that range.

Fermat, and later Euler, discovered methods that simplified the task of testing for primality in the case of Mersenne numbers. They proved that all factors of any M_p must be of the form 2kp + 1 and, at the same time, of the form 8n ± 1, where k and n are integers. For example, choosing k = 1 and 4, and n = 3 and 11, 2,047 = 23 x 89=(2 x 1 x 11 + 1) (2 x 4 x 11 + 1)=(8 x 3 - 1) (8 x 11 + 1). This discovery greatly reduces the number of possible factors of Mp, making it easier to test for primality. It allowed Euler to show that M₃₁ = 2,147,483,647 is indeed a prime.

In 1876, Edouard Lucas came up with a primality test suitable for all numbers, which also turned out to be particularly well tailored for testing Mersenne numbers. This test quickly showed that Mersenne's conjecture was incorrect. In 1930, D. H. Lehmer improved the Lucas method to form the basis for the test still used today. The algorithm for testing the primality of Mersenne numbers begins by setting the initial value of a function u equal to 4. A formula relates each successive new value of the function to the previous old value. That is, the new value u (i + 1) is equal to the remainder after the old value u(i) is squared, then decreased by 2 and divided by the Mersenne number itself. In mathematical terms, this is written as u(i + 1) = (u(i)² - 2)(mod M_p). Modular arithmetic strikes again! M_p is a prime if after going through this procedure up to but not including the value of p, the final remainder is zero. For example, if p = 5, M₅ = 2⁵ - 1 = 31; u(1) = 4; u(2) = (4² - 2)(mod 31)=14; u(3) =(14² - 2)(mod31)=8; u(4)=(8² - 2)(mod31)= 0. M₅ is a prime!

With the aid of high-speed computers, the Lucas-Lehmer test has turned out to be a relatively quick and easy way to test the primality of Mersenne numbers. In 1978, two California high-school students, Laura Nickel and Curt Noll, used 440 hours on a large computer to set the record for the highest known prime of that time. Their number, 2 ^21,701 - 1 was the twenty-fifth Mersenne prime discovered and has 6,533 decimal digits.

Thereafter, the pursuit quickly became a private game for the largest and fastest supercomputers. The historical record shows that it takes four times as much computation to discover the next Mersenne prime as it would to rediscover all previously known Mersenne primes. In a sense, the search for Mersenne primes can be seen as a measure of increases in computing power over the last two centuries.

One recent champion, the record holder of 1985, was found accidentally while a new supercomputer was being put through its paces to make sure the machine was functioning properly. The number, the thirtieth known Mersenne prime, has an exponent of 216,091 and runs to 65,050 decimal digits. The computer took about three hours to complete the 1.5 trillion calculations involved (see Figure 2.4). Where will the next mammoth prime be found? Are there an infinite number of Mersenne primes? No one knows yet.

Breaking up is hard to do

Further Reading

MAIN INDEX

REFERENCE GUIDE

TRANSCRIPTS

CIPHER-GLOSSARY