algorithm design techniques by the algorithm thusthis algorithm occasionally makes mistakebut we will see that the error ratio can be made arbitrarily negligible the key to the algorithm is well-known theorem due to fermat theorem (fermat' lesser theoremif is primeand pthen ap- (mod pproof proof of this theorem can be found in any textbook on number theory for instancesince is prime (mod this suggests an algorithm to test whether number is prime merely check whether - (mod nif - (mod )then we can be certain that is not prime on the other handif the equality holdsthen is probably prime for instancethe smallest that satisfies - (mod nbut is not prime is this algorithm will occasionally make errorsbut the problem is that it will always make the same errors put another waythere is fixed set of for which it does not work we can attempt to randomize the algorithm as followspick at random if an- (mod )declare that is probably primeotherwise declare that is definitely not prime if and we find that (mod thusif the algorithm happens to choose it will get the correct answer for although this seems to workthere are numbers that fool even this algorithm for most choices of one such set of numbers is known as the carmichael numbers these are not prime but satisfy an- (mod nfor all that are relatively prime to the smallest such number is thuswe need an additional test to improve the chances of not making an error in we proved theorem related to quadratic probing special case of this theorem is the followingtheorem if is prime and pthe only solutions to (mod pare proof (mod pimplies that (mod pthis implies ( )( (mod psince is prime pand must divide either ( or ( )the theorem follows thereforeif at any point in the computation of an- (mod nwe discover violation of this theoremwe can conclude that is definitely not prime if we use powfrom section we see that there will be several opportunities to apply this test we modify this routine to perform operations mod nand apply the test of theorem this strategy is implemented in the pseudocode shown in figure recall that if witness returns anything but it has proven that cannot be prime the proof is nonconstructivebecause it gives no method of actually finding the factors it has been shown that for any (sufficiently largenat most ( )/ values of fool this algorithm thusif is chosen at randomand the algorithm answers that is (probablyprimethen the algorithm is correct at least percent of the time suppose witness is run times the probability that the algorithm is fooled once is at most thusthe probability that independent random trials fool the algorithm is never more than