ABSTRACT
A number of primality tests exist that determine, with certainty, whether a large integer n is prime. However, the theory and implementation of these tests is rather involved. By contrast, pseudoprimality tests, which determine whether, with high probability (but not certainty), an integer is prime, are a lot faster and can much more easily be implemented. Methods for modular exponentiation and evaluation of recurrence sequences are widely employed in this context and are very efficient. The catch of tests based on these methods is the existence of “pseudoprimes,” i.e., composite numbers that are identified as primes by the test.
