ABSTRACT
In this chapter, the authors show how to decide whether a number is prime or composite. With the popularity of cryptographic algorithms that use primes, primality testing and factoring have become very important. The easiest method for primality testing and factorization is trial division. If authors look at odd numbers, then the chances are 1 in 115 that a number is prime. A good strategy is to look at the odd numbers, starting at a random starting point, and test each one. Since authors expect to encounter many more composites that primes, authors need a fast way to recognize composites. Pierre de Fermat's theorem comes to the rescue. For numbers of special forms, there are special primality tests that are more efficient than the general purpose ones that apply to all numbers. The chapter describes tests that apply to Fermat numbers and Mersenne numbers.
