4
$\begingroup$

Probabilistic primality testing methods like Rabin Miller and Solovay Strassen, were created at the time when mathematicians were not sure whether there is a deterministic polynomial algorithm.

After 2002 paper with a polynomial algorithm and it improved version which runs in $O(\log(n)^6)$ do we still need to use probabilistic methods for practical applications (cryptography)?

I can guess that the answer is yes, because they are faster, but I am interested to see how much faster are they for 4096 bit RSA keys. (or if I am wrong to know whether we still need them).

$\endgroup$
4
  • $\begingroup$ If I remember correctly, Rabin-Miller has complexity $O((\log n)^3)$, so the relation between running times would be about $C\cdot (2^{12})^3$ where $C$ is the quotient between the constant factors for $2^{12}$ bits. I don't know what the constants are, but it's unlikely that the quotient is much smaller than $1$, so you're probably looking at seconds for MR vs. years for AKS. $\endgroup$ Dec 12, 2014 at 12:47
  • $\begingroup$ @DanielFischer can you please tell add the source for RM complexity (I tried to find it, but was not able). Also for $2^{12}$, AKS would run approximately $12^6 \approxeq 10**7$ which is still below the second on a normal machine. $\endgroup$ Dec 12, 2014 at 19:47
  • 1
    $\begingroup$ For the running time, cf. wikipedia, $O(k(\log n)^3)$ if we do $k$ tests, which can be improved by using a better multiplication algorithm. For a $4096$ bit RSA key, note that $4096 = 2^{12} = \log n$, we have $2^{4095} \leqslant n < 2^{4096}$. So it's not $12^6$ vs. $12^3$ but $(2^{12})^6$ vs. $(2^{12})^3$. $\endgroup$ Dec 12, 2014 at 19:56
  • $\begingroup$ @DanielFischer thank you Daniel, I thought I have to take the logarithm from $2^a$ number $\endgroup$ Dec 12, 2014 at 20:05

2 Answers 2

7
$\begingroup$

You can see a graph and discussion of runtimes of some open source solutions, including BPSW (probable prime test), APR-CL, ECPP, and AKS in this answer to AKS usefulness. Reading your text, it looks like you might be asking "Did AKS have any impact on practical crypto implementations?", and the answer is "No."

Going with Charles' example, 2048 bits is 617 digits. The times I measured for random 600 digit primes (single thread on 4770K) were:

  • 0.007s BPSW
  • 28s APR-CL (WraithX)
  • 35s APR-CL (Pari)
  • 33s ECPP (mine)
  • 16.5s ECPP (Primo)
  • 465 years (est) AKS (my B+V)

Observed growth rates for my implementation and platform of $\log(n)^{2.4}$ for BPSW, $\log(n)^{3.6}$ for APR-CL, $\log(n)^{4.0}$ for ECPP (both versions), and $\log(n)^{6.4}$ for AKS (both v6 and B+V improvements). AKS is important for the theory, but not useful in implementations. Clearly BPSW is much faster than the proof methods. APR-CL may have a higher exponent as the size increases (this measurement only went to 2000 digits). Only ECPP of these methods gives a certificate.

As Charles points out, we really want to use pre-tests when checking primality for arbitrary numbers, such as the case of selecting random primes or calling a nextprime function. Trial division type testing is of course easy and gets rid of lots of composites. A BPSW test consists of a single M-R test with base 2, followed by some variant of a Lucas test. At this size, almost all composites will fail the single M-R test, so the actual time taken for them is only about 1/3 the time shown for primes.

Another interesting point: both ECPP implementations perform BPSW tests throughout the computation. It's very cheap compared to the cost of the other operations. So even when we use proofs, internally the code may be doing some probable prime tests.

For DSA, the Q size is typically 160-256 bits, so a proof is pretty easy (BLS75 or ECPP or APR-CL) and should only take a few milliseconds. I don't think many implementations actually do that however (I'm only aware of one). For the larger sizes (1024+ bits for DSA's P or RSA P/Q) it will start taking appreciable time and spending a little more time on more probable prime tests is likely to be a better payoff (e.g. more random-base M-R tests, add a Lucas or Frobenius test).

Also note that there are two common algorithms for creating random proven primes via construction: Shawe-Taylor and Maurer. Both build up random proven primes by using a chain of Pocklington (or BLS75 theorem 3 or 5) tests. This is fairly straightforward (FIPS 186-4 describes a Shawe-Taylor algorithm) and one can get a certificate output as well if desired. There is a penalty that not every possible prime can be created, but the papers discuss that and indicate it should not be a security issue for large sizes. Do note that I've seen broken implementations that can produce composites, so for mine I added BPSW tests for all partial results and verify the final certificate as well. While this method is faster for large sizes than taking a random probable prime and running a generic proof on it, it is slower than using a good random probable prime generator and adding some decent extra tests (so the resulting number has passed BPSW, a few additional random-base M-R tests, and a Frobenius test). Your implementations and needs may vary.

$\endgroup$
1
  • 1
    $\begingroup$ No composite number below 2^64 passes the Baillie–PSW test. There are also no known composite numbers above that bound that pass the test, in other words, there are no known Baillie–PSW pseudoprimes. en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test $\endgroup$
    – oittaa
    Apr 30, 2022 at 20:50
2
$\begingroup$

Here's some sample code for finding an RSA key: http://www.cypherspace.org/rsa/rsakg.c

It generates numbers uniformly at random, then tests them with mpz_probab_prime_p( , 25).

Finding a 4096-bit RSA key require generating two 2048-bit primes. In this case mpz_probab_prime_p will do trial division up to 4096, and then up to 25 Miller-Rabin tests. About 1 in 1418 2048-bit numbers numbers are prime, but after trial division the method only needs to try about 95.5 numbers on average to generate a prime. The composites will be discovered after about 1 iteration, while the prime will take 25 iterations, for a total of about 120 Miller-Rabin tests.

Some testing on my computer suggests that 120 Miller-Rabin tests take about 4.5 seconds.

If the AKS test was used it would require about 95 tests -- you wouldn't need to try multiple times. Extrapolating from Brent's notes, an AKS test at 2048 bits would take about 53000 years, or over 5 million years for all 95.

This can be improved, of course. You could use Miller-Rabin as a pretest, then switch to AKS. In that case the total time would be about 3.6 seconds for 95 Rabin-Miller pretests and 53000 years for the final AKS test, for a savings of about 5 million years.

So even if you want to use primality proving algorithms, Miller-Rabin is useful.

$\endgroup$
5
  • $\begingroup$ are you sure about 95 tests in AKS? I thought that AKS is deterministic algorithm, therefore there is nothing like tests there. $\endgroup$ Dec 13, 2014 at 0:16
  • $\begingroup$ @SalvadorDali: 95 tests because, on average, you'll have 94 composites and 1 prime. If you pretest to remove (almost) all of the composites you only need (slightly more than) one AKS test. $\endgroup$
    – Charles
    Dec 13, 2014 at 0:35
  • $\begingroup$ Small quibble: the rsakg.c program doesn't make uniform random primes. It uses the PRIMEINC algorithm which has a very uneven distribution (primes at the end of large gaps have a much higher chance of selection). It has the advantage of being 2-4x faster than good methods like random-index-selection, trivial, Joye/Paillier, or Fouque/Tibouchi. See the latter's 2011 paper for discussion. $\endgroup$
    – DanaJ
    Dec 15, 2014 at 16:40
  • $\begingroup$ @DanaJ: Indeed, you're right -- I must have misread the code, because I see now that they're doing as you say (taking nextprime(random), essentially). $\endgroup$
    – Charles
    Dec 15, 2014 at 20:30
  • $\begingroup$ @DanaJ: Actually, that inspires me to ask a new question: math.stackexchange.com/q/1069693/1778 Maybe you have some ideas? $\endgroup$
    – Charles
    Dec 15, 2014 at 21:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .