Time estimate to determine if a number is prime [closed]

Question

How long does it take to verify that a given number is a prime number, as a function of its number of digits, in a personal computer, say? How computationally hard is this?

Answer 1

Current versions of the AKS primality test give the answer in $O(d^{6+\epsilon})$ steps, where $d$ is the number of digits. Here $\epsilon>0$ is arbitrary and the $O$-constant depends on it. There are better algorithms for practical purposes, but their running time estimates depend on unproven hypotheses such as the Riemann Hypothesis for Dirichlet $L$-functions.

Answer 2

Below are some (very) lightly edited notes of mine that date from c. 2010, but should still be pretty good. The key for the present question to regard an RSA encryption and a primality test as roughly computationally equivalent.

---

Typical primality tests check for small prime factors up to some bound before using the Miller-Rabin probabilistic primality test. Trial division by primes $\le B$ will eliminate all but the approximate proportion $1.12/\log B$ of candidate primes. Thus only $0.3882 \cdot n/\log B$ candidate primes require using Miller-Rabin on average: this is 287 for $n = 4096$ and $B = 256$.

(NB. The AKS or other such primality test could be used to confirm a Miller-Rabin candidate prime, though in practice this requires spectacular effort for superfluous results. Faster methods to produce provable primes are used in practice, but are still generally considered superfluous.)

The computational complexity of a single Miller-Rabin test is $O(n^3)$, and in fact Montgomery modular exponentiation (and squaring) also plays a dominant role in typical implementations. Besides the modular exponentiation, a single Miller-Rabin test requires roughly a single modular multiplication on average (because on average $N-1$ has approximately 2 factors of 2: the number of such factors of 2 is one more than the worst-case number of modular squaring operations in a Miller-Rabin test), and we may disregard this in complexity analyses.

Assuming for simplicity that the complexity of a single Miller-Rabin test is roughly equivalent to long-exponent RSA encryption, for $n$ = 1024, 2048, and 4096 (recall that the primes involved are half these bitlengths and that two such primes must be generated) a 3 GHz processor core would yield roughly 32, 2, and 0.125 RSA moduli per second; since the key generation step is dominated by this we identify the two processes. These estimates are broadly consistent with runtimes observed in practice and correspond to the complexity estimate $1.3586 \times 10^{-3} \cdot n^4$.