The encryption program PGP takes advantage of this property of the theorem to test whether the large random numbers it selects are prime. It tests the values we'll call x using 4 values of a (referred to as witnesses) using the above formula. These 4 values are 2, 3, 5 and 7, the first four primes. If 1 = 2^{x1} = 3^{x1} = 5^{x1} = 7^{x1} (mod x), it knows that the number x is probably prime. If any of the equations comes up with a value other than 1, then x is definitely composite. Using additional witnesses decreases the chance that a composite x will appear to be prime, although very few large numbers can fool the 4 witnesses already listed.
The pseudoprime article gives an indepth discussion of numbers which fool primality tests such as these.
Search Encyclopedia

Featured Article
