# How does Python's pycrypto library generate primes?

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 functions 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?

## 1 Answer

The documentation is not directly telling the algorithm. One can check from the source code. getPrime uses isPrime and that calls the Rubin-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. It may be a prime in the Sieve or divisible by one of them. If none of the cases, then 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}$$

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$$

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.

• This answer feels slightly incomplete. It doesn't mention what isPrime gets run on in the first place (a randomly sampled $n$ bit number). – puzzlepalace Feb 5 at 18:46
• This generates a prime with a bias: the probability of a prime being selected grows linearly with how far above the previous prime it is. – fgrieu Feb 5 at 19:55
• @fgrieu this is due to the library's design or Rabin-Miller? – kelalaka Feb 5 at 20:01
• @kelalaka: this is due to moving to the next candidate prime with number=number+2, rather than drawing a new random number, or moving to the next one with a more sophisticated procedure. – fgrieu Feb 5 at 20:07
• @fgrieu assuming that getPrime succeeds after considering a relatively small number of candidates (say, no more than 10^100) it means the process selects a prime from the region between a truly random x and x+2*10^100. For 2048 bit numbers, that's pretty much a uniform distribution, as the relative bias is 2*10^100 / 2^2048 ≈ 10^-516 ≈ 0. A much more serious issue is the 10^-6 possibility of false positives. – Peteris Feb 5 at 20:56