ABSTRACT
Two fundamental computational problems in number theory are finding large primes and factoring composite numbers. Although these problems are related, they have intrinsic differences. It is relatively easy to prove that a number is composite but, once this has been done, it is much harder to find its factors. With the popularity of cryptographic algorithms that use primes, primality testing and factoring have become very important. In this chapter, we show how to decide whether a number is prime or composite. Then we discuss some factorization methods that are used in practice.
