The Density of Primes

Most cryptologic schemes need large prime numbers. Hence it is important to know how many prime numbers of a certain size there are. 

The basic theorem in this field is the well-known prime-number theorem. 

Sometimes, primes in certain congruence classes are needed, e.g., p = 3 mod 4 for Blum integers. For such cases, Dirichlet s prime-number theorem states that in a certain sense, primes are equally distributed over the possible congruence classes Given any modulus v, there are roughly equally many primes congruent mod v for all 6 Zy. If denotes the number of primes in the set 1, that 

The prime-number theorems considered all the primes up to a certain limit. If one is only interested in large primes, e.g., primes with a given binary length k, the following statement is more interesting For all n N  

The proof is a rather straightforward application of Dirichlet s prime-number theorem and some o-calculus. 

---

Prekey generation is of the same order of complexity as key generation in ordinary digital signature schemes It is dominated by the primality tests needed for the generation of two primes, q and p. This means approximately one exponentiation per number tested for primality with the Rabin-Miller test. Hence the number of exponentiations is determined by the density of primes of the chosen size (see Section 8.1.5) however, many numbers can be excluded by trial division as usual. 

Clearly, some paths are more strategic than others. A prime factor of N cannot exceed It makes little sense, however, to commence a factoring job by searching for and testing primes near This is because the density of primes scales as 1/ loge(A). For arbitrary N, it is more likely that low-valued integers have prime status and prove to be viable factors. After all, 50% of integers have 2 as a prime factor. 

---