Fermat Prime Test Effectiveness\302\2512007 by Mike May, S.J., Saint Louis University - maymk@slu.edurestart:In class we looked at a the Fermat test as a quick method for checking if a number is composite. If a^(n-1) is not congruent to 1 mod n, then a is a Fermat witness that n is not prime. We also noted that this test does not always work, so we developed the Miller-Rabin test which theoretically identifies a composite number at least 75% of the time. This worksheet looks at how effective simple Fermat test is with numbers f various sizes. We will see that for since we are interested in testing numbers of at least 80 digits to see if they are prime, with numbers of that size the Fermat test with a single alpha is incredibly efficient.The first step is to create a modification of the rand function that returns random odd integers greater than 1.oddRand := proc(magN)
local TrialNumber:
TrialNumber := rand(3..10^magN)():
TrialNumber := TrialNumber + 1 - (TrialNumber mod 2):
end proc:n := oddRand(80);
<Text-field style="Heading 1" layout="Heading 1">Testing many witnesses for a single number n</Text-field>One method of checking efficiency of the Fermat test is to ask for a given composite number n, how many candidates fail to witness that n is composite.We need to create a function that will take a pair (n,m) and tell us that either n is prime, or will test the first m integers starting with 2 and see if they are witnesses that n is composite. The procedure will tell us for a composite n how many of these m candidates fail to witness that n is composite.witnessTest := proc(n,m)
local badWitness, i:
badWitness := 0:
if (isprime(n)) then print(n, " is prime"):
else
for i from 2 to (m+1) do
if ((Power(i, n-1) mod n) = 1) then
print(i, " fails to withness ", n, " is composite."):
badWitness := badWitness + 1:
end if:
end do:
print(badWitness, " of the first ", m, " candidates failed to witness."):
end if:
end proc:n := n;
witnessTest(n,200);Putting the two procedures together lets us test random odd integers of a specified size.n := oddRand(4);
witnessTest(n,200);It is interesting to try this several times with the degree of n set at 3, 4, and 5. My experience from simply repeating the code above many times is that by the time the degree of n is 6, we expect most composite n will have no Fermat liars in the first 200 numbers. If the order of n is small we can also try letting m = n-3, testing with 2 through n-2..n := oddRand(6);
witnessTest(n,n-3);
<Text-field style="Heading 1" layout="Heading 1">Testing primeness with many n and many witnesses</Text-field>The next test of efficiency is to check the Fermat test with a fixed number of candidates and see how many composite numbers in a range we failed to correctly identify as composite.We need a procedure that would try numRand random odd numbers of order sizeRand, and tell us how many are prime, and how many of the first numCand candidates fail to witness to each composite.CandidateTester := proc(numRand, sizeRand, numCand)
local falseWitness, numberPrimes, nCount, i, test, n:
falseWitness := 0:
numberPrimes := 0:
for nCount from 1 to numRand do
n := rand(2..10^sizeRand)():
n:= n + 1 + (n mod 2):
if (isprime(n))
then numberPrimes := numberPrimes + 1:
else
for i from 2 to numCand + 1 do
test := (Power(i, n-1) mod n):
if ((Power(i, n-1) mod n) = 1)
then print (i, "is fails to witness for the composite ", n):
falseWitness := falseWitness + 1:
end if;
end do:
end if:
end do:
print(numberPrimes, " primes found");
print(falseWitness, " cases where a number failed to witness to a composite"):
end proc:We can use this to look at what happens with 1000 random numbers chosen at various sizes with 10 candidates tested at each n. Thus we are trying 10,000 tests at each size.for i from 4 to 15 do
CandidateTester(1000,i,10);
print("After testing 1000 numbers about the size of 10^",i):
end do:As the size of the candidate numbers rises from 10^4 to 10^15, the number of primes found in 1000 tries fell from something around 250 to somewhere around 65 primes. The number of Fermat liars with 10,000 tests fell from from about 80 when n n is about 10^4, to 20 when n=6 to no cases when n is larger than 8.Experimentally, by the time randSize is at least 10, potential candidates fail to witness in less than 1 in 100,000 cases.
<Text-field style="Heading 1" layout="Heading 1">Checking efficiency of testing primeness using a single Fermat witness</Text-field>Given the efficiency we have seen, we are ready for a third test of efficiency of the Fermat testFor 80 digits numbers we can test how often testing a candidate n with a single fails to witness that n is composite. To make the computer not look like it is frozen, we will print out results after every 5000 tests.for i from 1 to 20 do
CandidateTester(5000,80,1);
print("After testing 5000 numbers about the size of 10^",80):
end do:Checking 100,000 odd numbers of size 80 found about 1000 primes and no cases where checking with the Fermat test a single time did not correctly identify composite numbers.We would like to look generalize the investigation above and look at how often we fail to spot a composite number by simply trying the Fermat test with a = 2. For this procedure we eliminate the random number and instead ask for a starting point and a number of odd numbers to check.twoCandidateTester := proc(startNumber, numCand)
local falseWitness, numberPrimes, nCount, test, temp:
falseWitness := 0:
numberPrimes := 0:
test := startNumber + 1 - (startNumber mod 2):
print(test, numCand):
for nCount from 1 to numCand do
if (isprime(test))
then numberPrimes := numberPrimes + 1:
else
temp := (Power(2, test-1) mod test):
if (temp = 1) then:
print ("2 fails to witness for the composite ", test):
falseWitness := falseWitness + 1:
end if;
end if:
test := test + 2:
end do:
print(numberPrimes, " primes found");
print(falseWitness, " cases where 2 failed to witness to a composite"):
end proc:twoCandidateTester(10^6, 10^5);We can speed things up by only printing out the number of instances.twoCandidateTester2 := proc(startNumber, numCand)
local falseWitness, numberPrimes, nCount, test, temp:
falseWitness := 0:
numberPrimes := 0:
test := startNumber + 1 - (startNumber mod 2):
print("Starting with ",test, " and checking ", numCand, " odd numbers"):
for nCount from 1 to numCand do
if (isprime(test))
then numberPrimes := numberPrimes + 1:
else
temp := (Power(2, test-1) mod test):
if (temp = 1) then:
falseWitness := falseWitness + 1:
end if;
end if:
test := test + 2:
end do:
print(numberPrimes, " primes found");
print(falseWitness, " cases where 2 failed to witness to a composite"):
end proc:twoCandidateTester2(10^5, 10^5);
twoCandidateTester2(10^80, 10^5);
<Text-field style="Heading 1" layout="Heading 1">Checking efficiency of testing primeness using a single Rabin witness</Text-field>We are now ready to check how effective our prime testing is when we use the Miller-Rabin test with a single test number.The next procedure checks Miller-Rabin for 2 on the cases the first test failed on.twoCandidateTester3 := proc(startNumber, numCand)
local falseWitness1, falseWitness2, numberPrimes, nCount, test,
temp, exp2, tExp, test1, eCount:
falseWitness1 := 0:
falseWitness2 := 0:
numberPrimes := 0:
test := startNumber + 1 - (startNumber mod 2):
print("Starting with ",test, " and checking ", numCand, " odd numbers"):
for nCount from 1 to numCand do
if (isprime(test))
then numberPrimes := numberPrimes + 1:
else
temp := (Power(2, test-1) mod test):
if (temp = 1) then:
falseWitness1 := falseWitness1 + 1:
exp2 := test-1:
while (temp =1) do
exp2 := exp2/2:
temp := (Power(2, exp2) mod test):
test1 := ((temp +1) mod test):
if (test1 = 0) then
falseWitness2 := falseWitness2 + 1:
print("2 failed to witness for the Miller-Rabin test for ",test):
elif (test1 > 2) then
print("2 is a witness for Miller-Rabin for ", test):
print("2^",exp2,"=",temp," and 2^",2*exp2,"= 1");
end if:
if ((exp2 mod 2) = 1) then temp := 0 end if:
end do:
end if;
end if:
test := test + 2:
end do:
print(numberPrimes, " primes found");
print(falseWitness1, " cases where 2 failed to witness to a composite"):
print(falseWitness2, " cases where 2 failed to Witness Miller-Rabin"):
end proc:twoCandidateTester3(10^4, 10^4);Finally we produce a last procedure simply gives summary results.twoCandidateTester4 := proc(startNumber, numCand)
local falseWitness1, falseWitness2, numberPrimes, nCount, test,
temp, exp2, tExp, test1, eCount:
falseWitness1 := 0:
falseWitness2 := 0:
numberPrimes := 0:
test := startNumber + 1 - (startNumber mod 2):
print("Starting with ",test, " and checking ", numCand, " odd numbers"):
for nCount from 1 to numCand do
if (isprime(test))
then numberPrimes := numberPrimes + 1:
else
temp := (Power(2, test-1) mod test):
if (temp = 1) then:
falseWitness1 := falseWitness1 + 1:
exp2 := test-1:
while (temp =1) do
exp2 := exp2/2:
temp := (Power(2, exp2) mod test):
test1 := ((temp +1) mod test):
if (test1 = 0) then
falseWitness2 := falseWitness2 + 1:
print("2 failed to witness for the Miller-Rabin test for ",test):
end if:
if ((exp2 mod 2) = 1) then temp := 0 end if:
end do:
end if;
end if:
test := test + 2:
end do:
print(numberPrimes, " primes found");
print(falseWitness1, " cases where 2 failed to witness to a composite"):
print(falseWitness2, " cases where 2 failed to Witness Miller-Rabin"):
end proc:We can now try this for various size numbers.for i from 4 to 7 do
twoCandidateTester4(10^i, 10^5);
end do;for i from 0 to 30 do
twoCandidateTester4(10^10+i*2*10^5, 10^5);
end do:Thus by the time we have n = 10^10, the next 3,000,000 odd numbers contain 250,000 primes and a 4 composite numbers where 2 fails to witness with the simple prime test. In 2 of these cases, the Miller-Rabin test also fails.for i from 0 to 20 do
twoCandidateTester4(10^20+i*10^5, 5*10^4);
end do:Thus by the time we have n = 10^20, the next 1,000,000 odd numbers contain 25,000 primes and no composite numbers where 2 fails to witness with the simple Fermat prime test.For extra credit see if you can find a composite number of more than 100 digits where 2 fails to witness for the Fermat test.Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.