6
$\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 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?

$\endgroup$
9
$\begingroup$

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.

| improve this answer | |
$\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 '19 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 '19 at 19:55
  • $\begingroup$ @fgrieu this is due to the library's design or Rabin-Miller? $\endgroup$ – kelalaka Feb 5 '19 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 '19 at 20:07
  • 1
    $\begingroup$ 1e-6 is a worst case probability that isPrime yields true for any fixed composite integer, and is a fair estimate for a Carmichael number. However these get vanishingly rare when moving to large ones, and for other composites the probability that isPrime yields true is much lower, and tends to decreases when the number gets larger. Therefore the probability that getPrime returns a composite is much lower than 1e-6 (which would be perfectly detectable, and a serious issue). $\endgroup$ – fgrieu Apr 25 at 12:41

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.