This chapter studies methods of constructing large probable primes. The pseudoprime and strong pseudorpime tests are methods by which it is possible to construct large probable primes for applications to public-key cryptography. These tests are sufficient in practice for constructing primes for applications.
Methods for constructing large provable primes are explored in the next chapter.
This chapter also includes a detailed discussion of two factoring mehtods, the Pollard (p-1) and rho-methods. The (p-1)-method is the basis of several other methods, including the elliptic curve factorig method.