In this post, we discuss a primality testing exercise involving the eighth Fermat number. A Fermat number is of the form where is any nonnegative integer. We search for the first prime number that is greater than . The basic idea is to search for the first probable prime base 2 among the odd numbers after . Once the first probable prime base 2 is identified, we apply the Miller-Rabin primality test to confirm that it is a prime number. At the outset of this exercise, we did not know how many numbers we had to check before reaching the first prime number.

The first five Fermat numbers , , , and are the only Fermat numbers that are known to be prime (it was conjectured by Fermat that all Fermat numbers are prime). It is unknown whether there exists prime Fermat number beyond . What is clear, however, is that all the higher Fermat numbers that were studied turn out to be composite. The 8th Fermat number has 78 decimal digits with two factors with 16 and 62 digits (it was factored in 1961). The largest Fermat number that has been completely factored (as of the writing of this post) is which has 617 decimal digits. Many Fermat numbers larger than have been partially factored.

___________________________________________________________________

**The basic approach**

The following is the number , which has 78 decimal digits.

11579208923731619542357098500868790785326998466564

0564039457584007913129639936

Define where is an odd positive integer, i.e., . The exercise is to find the smallest such that is a prime number. According to Euclid’s proof that there are infinitely many prime numbers, such a is sure to exist. Just that we do not know at the outset how far we have to go to find it. Of course, is the 8th Fermat number, which is a composite number with two prime factors with 16 and 62 decimal digits. So the search starts with .

The key is to do the following two quick checks to eliminate composite numbers so that we can reach a probable prime as quickly as possible.

- For any given , the first step is to look for small prime factors, i.e., to factor using prime numbers less than a bound . If a small prime factor is found, then we increase by 2 and start over. Note that we skip any where the sum of digits is divisible by 3. We also skip any that ends with the digit 5.
- If no small factors are found, then compute the congruence . If the answer is not congruent to 1, then we know is composite and work on the next number. If , then is said to be a probable prime base 2. Once we know that a particular is a probable prime base 2, it is likely a prime number. To further confirm, we apply the Miller-Rabin primality test on that .

In the first check, we check for prime factors among the first 100 odd prime numbers (i.e. all odd primes up to and including 547).

___________________________________________________________________

**Searching the first probable prime**

At the outset, we did not know how many numbers we will have to check. Since there can be a long gap between two successive prime numbers, the worse fear is that the number range we are dealing with is situated in such a long gap, in which case we may have to check thousands of numbers (or even tens of thousands). Luckily the search settles on a probable prime rather quickly. The magic number is 297. In other words, for the number

, we find that . Thus is a probable prime in base 2. The following shows the decimal digits of .

11579208923731619542357098500868790785326998466564

0564039457584007913129640233

To further give a sense of how the magic number is reached, the following table lists the 25 calculations leading to the magic number.

The first number is in the table ends in a 5 and is thus composite. The third number is composite since the sum of the digits of its is divisible by 3. The third column of the above table shows the least prime factor below 547 (if one is found). An asterisk in the third column means that none of the prime numbers below 547 is a factor. For such numbers, we compute the modular exponentiation .

In the above table, 4 of the asterisks lead to the result . These numbers are thus composite. For example, for , the following is the result:

55365573520609500639906523255562025480037454102798

631593548187358338340281435

The last number in the table is a probable prime base 2 since our calculation shows that . Being a probable prime to base 2 is actually very strong evidence that the number is a prime number. We want even stronger evidence that is a prime. For example, we can carry out the Miller-Rabin test in such a way that the probability of mistaking a composite number as prime is at most one in a septillion! A septillion is the square of a trillion. A trillion is . Thus a septillion is . One in a septillion is for all practical purposes zero. But if one wants more reassurance, one can always run the Miller-Rabin test with more bases.

___________________________________________________________________

**The Miller-Rabin primality test**

The Miller-Rabin test is a variant of the Fermat test because Miller-Rabin still relies on Fermat’s little theorem. But Miller-Rabin uses Fermat’s little theorem in such a way that it eliminates the issue of the Fermat test mistakenly identifying Carmichael numbers as prime.

Given an odd positive integer whose “prime or composite” status is not known, the Miller-Rabin test will output “composite” or “probable prime”. Like the Fermat test, the Miller-Rabin test calculates for several values of . But the test organizes the congruence a little differently to capture additional information about prime numbers.

Here’s how to set up the calculation for Miller-Rabin. Because is odd, is even. We can factor as a product of a power of 2 and an odd number. So we have where and is odd ( may not be prime). Then we calculate the following sequence:

The first term in (1) can be calculated using the fast powering algorithm (using the binary expansion of to convert the calculation of into a series of squarings and multiplications). Each subsequent term is then the square of the preceding term. The last term is of course . Each squaring or multiplication is reduced modulo . The Miller-Rabin test is based on the following property of prime numbers:

- At least one term in the sequence (1) is congruent to 1 modulo .
- Either the first term in (1) is congruent to 1 modulo or the term preceding the first 1 is congruent to -1 modulo .

*Theorem 1*Let be an odd prime number such that where and is odd. Let be a positive integer not divisible by . Then the following two conditions are true about the sequence (1).

*How the Miller-Rabin test works*

Suppose that the “prime or composite” status of an odd integer is not known. If both conditions in the above theorem are satisfied with respect to the number , then is said to be a strong probable prime in base . If a strong probable prime in base happens to be composite, then it is said to be a strong pseudoprime in base . In other words, a strong pseudoprime is a composite number that possesses a prime-like property, namely it satisfies the two conditions in Theorem 1 with respect to one base .

The test procedure of Miller-Rabin is to check whether is a strong probable prime to several bases that are randomly chosen. The following determines the outcome of the test:

- If is not a strong probable prime in one of the chosen bases, then is proved to be composite.
- If is shown to be a strong probable prime in all the chosen bases (say there are of them), then is “probably prime” with an error probability of at most .

To prove the integer is composite, we look for a base for which is not a strong probable prime. Such a value of is also called a Miller-Rabin witness for the compositeness of . For primality, the Miller-Rabin test does not give a mathematical proof that a number is prime. The Miller-Rabin test is a probable prime test. It gives strong evidence that is a prime number, with an error probability that can be made arbitrarily small by using a large random sample of values of .

Take the prime candidate that is discussed above. We plan to run the Miller-Rabin test on using 40 random values of where . If is shown to be a strong probable prime in all 40 bases, then the prime candidate is likely a prime number with an error probability of at most . This probability works out to be less than 1 in 10 raised to 24 (hence the one in a septillion that is mentioned earlier). If one wants stronger evidence, we can compute for more values of . Thus if is in actuality a composite number, there is at most a one in septillion chance that the Miller-Rabin test will declare is a prime number.

How can the Miller-Rabin test make the claim of having such a small error probability? The fact the the error probability of Miller-Rabin can be made arbitrarily small stems from the following fact.

*Theorem 2*Suppose that is a composite odd number. At most 25% of the numbers in the interval are bases in which is a strong pseudoprime. Putting it in another way, at least 75% of the numbers in are bases in which is not a strong pseudoprime.

To paraphrase Theorem 2, if is composite to begin with, at least 75% of the numbers in will prove its compositeness. That means that at most 25% of the numbers will exhibit the prime-like property described in Theorem 1. The power of Miller-Rabin comes from the fact that for composite numbers there are more values of that will give a correct result (in fact, at least 3 times more).

Thus if you apply the Miller-Rabin test on a composite number , you will bound to stumble on a base that will prove its compositeness, especially if the bases are randomly chosen. Any random choice of where has at least a 75% chance of being correct on the composite number . In a series of 100 random choices of , it will be hard to miss such values of . The only way that Miller-Rabin can make a mistake by declaring a composite number as prime is to pick all the values of from the (at most) 25% of the pool of values of that are strong pseudoprime prime. This probability is bounded by (if is the number of selections of ).

___________________________________________________________________

**Applying Miller-Rabin on the prime candidate**

The first task is to factor . We find that where is the following odd number:

14474011154664524427946373126085988481658748083205

070504932198000989141205029

For each randomly selected , we calculate the following sequence:

The first term is calculated using the fast powering algorithm (a series of squarings and multiplications). Each subsequent term is the square of the preceding term. Each term in the sequence is reduced modulo . The goal is to see if the two conditions in Theorem 1 are satisfied. One is that one of the 4 values in (2) is a 1. The other is that the term preceding the first 1 in (2) has to be a -1.

The following shows the 40 numbers that are randomly chosen in the interval .

03006957708701194503849170682264647623506815369915

7798209693214442533348380872

02223067440101780765895379553626469438082041828085

0568523022714143509352911267

04531895131849504635258523281146698909008537921009

6337435091877410129499153591

05434508269932993379745836263818598804800824522102

0278113825689716192402178622

08799241442673378780142202326330306495270149563840

3866810486309815815031353521

02638607393577034288802880492058261281940769238659

8928068666401909247319838064

04283430251977183138176255955338099404217762991191

9192783003754562986178981473

09773398144692973692102006868849010147546139698798

3443958657834362269077067224

05504666974469005713839308880951115507992521746498

7157086751623602877205126361

11369425784373951812019794994427515082375862595853

6524984616385315102874812557

11280428157869817083329641054154150272024966029283

2165114734540900026838117128

11208322317253928483879618989535357346499197200982

7728283667193655956607063861

05585951853297694372636067012444311272073854408338

4421611399136081624631900538

06831924581003106427566658433259804779354874917795

9811865334330929987281859876

07339174229323952008915772840377019251465052264221

1294344032116313026124007734

05117387267263929174559713098463717229625661656017

7194611080485470890280573816

06599941646668915168578091934085890873056463577356

8090503454939353325803291530

07545265152740184887140788322673806569482388835389

5577110370797470603035554930

02591621894664804222839429868664505564743756550515

2520842332602724614579447809

04791002227899384351266879075743764807247161403811

8767378458621521760044966007

03251071871924939761772100645669847224066002842238

6690935371046248267119967874

07211128555514235391448579740428274673170438137060

9390617781010839144521896079

02839820419745979344283855308465698534375525126267

1701870835230228506944995955

06304631891686637702274634195264042846471748931602

4893381338158934204519928855

06492095235781034422561843267711627481401158404402

2978856782776323231230432687

11078868891712009912929762366314190797941038596568

5459274315695355251764942151

05795069944009506186885816367149671702413127414386

2708093175566185349033983346

01712922833914010148104423892201355622294341143990

7524285008693345292476544524

09743541325262594740093734822046739122734773994479

9814337973200740861495044676

02503872375817370838455279068302037475992008315394

2976462871038003917493744995

06980677383898331402575574511880992071872803011356

6498794763450065008785347168

01507075889390134242331585173319278262699562685820

7121480322563439665642035394

02471785068822350832987019936892052187736451275830

5372059292781558599916131031

10950891460180297156465120507537244257810396062906

9207306297501015755045004254

11052976297188507170707306917942099264941855478856

2965936913589165233381674539

03911878231948499128291863266472008604449261315172

1053813631612297577166335941

06903294587603383022211116535092146484651980588002

9291840261276683214113088012

03942020579038616658412018517396703874933208670283

3087287933190554281896471934

04338728160253711124705740270085271024911573570055

1690460857511205663297661796

06707597137792150532106913489524457238449067437061

7211249957355483821516113140

For each random number , we calculated the 4 numbers indicated in sequence (2). The following 3 tables show the results of the calculation.

There are 4 columns of calculation results, one for each term in sequence (2). If a calculation result is a blank in the above tables, it means that the result is a number that is not 1 or -1 modulo . For example, and are congruent to the following two numbers:

86168678768024029811437552745042076645410792873480

629834883948094184848812907

10235477176842589582260882228891913141693105976929

7597880545619812030150151760

In the above 3 tables, all results match the conditions of Theorem 1. For each number , the calculated results are eventually 1. On some of the rows, the first result is a 1. In all the other rows, the term right before the first 1 is a -1. For example, in the first row where , the first 1 and the term preceding that is a -1.

The results in the above 3 tables show that the number is a strong probable prime in all 40 of the randomly chosen bases. We have very strong evidence that the number is a prime number. The probability that it is a composite number but we mistakenly identify it as prime is at most one in a septillion!

___________________________________________________________________

**Exercise**

In our search for probable primes larger than the 8th Fermat number, we also find that the number is also a probable prime base 2. The following shows the decimal digits:

11579208923731619542357098500868790785326998466564

0564039457584007913129640237

Is it a prime number? Perform the Miller-Rabin test on this number.

___________________________________________________________________