ABSTRACT

For long-term security of the RSA cipher, the primes in the modulus should be 154 digits (512 bits) each ensuring a modulus of 308 digits (1024 bits). Hence, it is essential to generate large “random primes” (see Remark 1.13 ). To do this, we generate large random numbers and test them for primality using primality testing algorithms. The fastest known such algorithms are probabilistic algorithms (those that use random numbers — see the discussion of randomized algorithms on page 205). This is in contrast to deterministic algorithms, also discussed on page 205. (See Exercises 4.1-4.5, where some deterministic primality testing algorithms, also called primality proofs may be found). Moreover, there are much faster (compared to deterministic) probabilistic algorithms for primality testing. There exist several general types of probabilistic algorithms, which we now describe. (If necessary, the reader may review complexity theory in Appendix B before proceeding.)

Types of Probabilistic Algorithms The following probabilistic algorithms are based upon decision problems

— those problems whose solution is either “yes” or “no” (see the discussion of problem classification on page 207). In each of the following algorithms, there is an assigned error probability or failure probability (computed over all possible random choices made by the algorithm when it is run with a given input), α ∈ R such that 0 ≤ α < 1. This means that the algorithm will give an incorrect answer with probability at most α. However, by running the algorithm a sufficient number of times, we may reduce α to a value as small as desired.