PseudoPrimeTest

A famous probabilistic primality test makes use of Fermat's Little Theorem from number theory. The theorem states

         p-1
	b     %   p  =  1

for all primes p, with b satisfying 1 < b < p, and % denoting modulus or remainder. To refresh your memory, a prime is an integer greater than 1 whose only factors are 1 and itself. In order to test some potential prime q we do the following:

• Choose some b-value and compute b^(q-1) % q.
• If this value is not 1 then you know q is not prime.
• If this value is 1, then you are more sure q is prime than before.

Given q you will try each b-value beginning with 2 until you reach q-1. If at least one of the b-values fails the test stated above (do not produce 1) then return the lowest failing b-value. If all pass return q.

When computing b^(q-1) % q the numbers can get enormous unless certain measures are taken. For one thing, after each multiplication you can apply the modulus. For example,

	190^11 % 300  =  ((190^5 % 300) * (190^6 % 300)) % 300  .

In addition, repeated squaring can speed up the exponentiation process. For example,

	a^9 = a*a*a*a*a*a*a*a*a      requires 8 multiplications but
        a^9 = a*((a^2)^2)^2          requires 4 multiplications.

We can combine the two methods above as illustrated in the following example where we compute a^11 % 12:

	a^11 % 12 = (a * (a^10 % 12)) % 12 
        a^10 % 12 = (a^5 % 12)^2 % 12 
        a^5  % 12 = (a * (a^4 % 12)) % 12 
        a^4  % 12 = (a^2 % 12)^2 % 12 
	a^2  % 12 = (a*a) % 12