4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This answer feels slightly incomplete. It doesn't mention what isPrime gets run on in the first place (a randomly sampled $n$ bit number). $\endgroup$ – puzzlepalace Feb 5 at 18:46
  • 1
    $\begingroup$ 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. $\endgroup$ – fgrieu Feb 5 at 19:55
  • $\begingroup$ @fgrieu this is due to the library's design or Rabin-Miller? $\endgroup$ – kelalaka Feb 5 at 20:01
  • 1
    $\begingroup$ @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. $\endgroup$ – fgrieu Feb 5 at 20:07
  • $\begingroup$ @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. $\endgroup$ – Peteris Feb 5 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.