Rabin-Miller test

An alternative to the use of the Rabin-Miller test are algorithms as in [Maur95] that generate numbers that are always prime, but with an unproven distribution. 

The algorithm group verification, on input ( 1 , q,p), first tests if I l2 Ipl2 2 len p(lc) this can be done in time polynomial in k. If yes, it continues and tests if > 2 and q I (p-1), and if p and q are prime. As discussed with the factoring assumption, the Rabin-Miller test is used in practice, although it introduces an exponentially small error probability into some properties (but not into availability of service). These tests take time polynomial in the length of q and p, which were already verified to be polynomial in k. 

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. 

Prekey verification A fixed small number of exponentiations, such as 12 (with 5 iterations of the basic Rabin-Miller primality test for q and p each). 

---