 Approaches to generating large prime numbers

To motivate the organization of this chapter and introduce many of the relevant concepts, the problem of generating large prune numbers is first considered. The most natural method is to generate a random number n of appropriate size, and check if it is prime. This can be done by checking whether n is divisible by any of the prime numbers < -Jn. While more efficient methods are required in practice, to motivate further discussion consider the following approach:

• 1. Generate as candidate a random odd number n of appropriate size.
• 2. Test n for primality.

A slight modification is to consider candidates restricted to some search sequence starting from n; a trivial search sequence which may be used is n, n + 2.» + 4. n + 6.____Using specific search sequences may allow one to increase the expectation that a candidate is prune, and to find primes possessing certain additional desirable properties a priori.

In step 2, the test for primality might be either a test which proves that the candidate is prime (in which case the outcome of the generator is called a provable prime), or a test which establishes a weaker result, such as that n is “probably prime” (in which case the outcome of the generator is called a probable prime). In the latter case, careful consideration must be given to the exact meaning of this expression. Most so-called probabilistic primal- itу tests are absolutely correct when they declare candidates n to be composite, but do not provide a mathematical proof that n is prime in the case when such a number is declared to be “probably” so. In the latter case, however, when used properly one may often be able to draw conclusions more than adequate for the purpose at hand. For this reason, such tests are more properly called compositeness tests than probabilistic primality tests. True primality tests, which allow one to conclude with mathematical certainty that a number is prime, also exist, but generally require considerably greater computational resources.

While (tine) primality tests can determine (with mathematical certainty) whether a typically random candidate number is prime, other techniques exist whereby candidates n are specially constructed such that it can be established by mathematical reasoning whether a candidate actually is prime. These are called constructive prime generation techniques.

A final distinction between different techniques for prime number generation is the use of randomness. Candidates are typically generated as a function of a random input. The technique used to judge the primality of the candidate, however, may or may not itself use random numbers. If it does not, the technique is deterministic, and the result is reproducible; if it does, the technique is said to be randomized. Both deterministic and randomized probabilistic primality tests exist.

In some cases, prime numbers are required which have additional properties. For example, to make the extraction of discrete logarithms hi Z* resistant to an algorithm due to Pohlig and Heilman (§3.6.4), it is a requirement that p— 1 have a large prime divisor. Thus techniques for generating public-key parameters, such as prune numbers, of special form need to be considered.

Distribution of prime numbers

Let ж(х) denote the number of primes in the interval [2, x. The prime number theorem (Fact 2.95) states that тг(х) ~ j^. In other words, the number of primes in the interval

[2. x] is approximately equal to ^. The prime numbers are quite uniformly distributed, as the following three results illustrate.

4.1 Fact (Dirichlet theorem) Ifgcd(a, n) = 1, then there are infinitely many primes congruent to a modulo n.

A more explicit version of Dirichlet’s theorem is the following.

4.2 Fact Let 7r(x, n, a) denote the number of primes in the interval [2, x] which are congruent to a modulo n, where gcd(a, n) = 1. Then In other words, the prime numbers are roughly uniformly distributed among the ©(») congruence classes in Z*, for any value of n.

4.3 Fact (approximation for the nth prime number) Let pn denote the nth prime number. Then pn ~ n In n. More explicitly, •  'if f(x) and g(x) are two functions, then f(x) ~ g(x) means that limx->oo = 1.