How does Python's pycrypto library generate primes?

Question

The pycrypto library in Python can generate random n-bit prime numbers. The syntax I use is as follows:

from Crypto.Util import number
number.getPrime(2048)

The above function has a very impressive performance and returns primes with a very small delay. What is the process used to generate such large primes in such short time periods in this function?

Answer 1

The documentation is not directly telling the implemented algorithm. One can check from the source code. getPrime uses isPrime and that calls the Rabin-Miller Primality test.

• getPrime generates a random odd number $\texttt{N}$ and calls isPrime

  number=getRandomNBitInteger(N, randfunc) | 1
       while (not isPrime(number, randfunc=randfunc)):
           number=number+2
  

• isPrime first checks for evenness and for pre-calculated Sieve primes, that list is the first 10000 primes. It may be a prime in the Sieve or divisible by one of them. If none of the cases, then the Rabin-Miller test is performed.

The Probability: The returned value of getPrime, if a probable prime, then the probability is given by $$ 1 - \frac{1}{4^k}$$ where $k$ is the number of iterations.

The Number of iterations: The Library defines

false_positive_prob=1e-6

calculates the $k$ by

k = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))

and from this, the number of iteration in the library is $k=10$.

Note that In my undergraduate, we used $k=20$. That makes false positive in the worst case 1e-12 where the library has 1e-6.

The Complexity: If modular exponentiation by repeated squaring is used then the complexity is $\mathcal{O}(k \log^3 n)$ where $k$ is the number of iterations to test that determines the probability.