Currently, the largest prime know is a mersenne, $2^{82,589,933} − 1$. That’s an $82,589,933$-bit number if I am correct. Considering that RSA codes of as low as 1024 bits can be considered safe, how was this number factored to check if it is prime? I can kind of answer that question myself, I am aware of the existence of a special, much faster, prime check for Mersenne primes. But, given a non special number of similar size, would we even be able to check if it was prime? How long would it take? How fast are the fastest prime checking algorithms for non-special form numbers?
5 Answers
The answer is it wasn't factored to show it was a prime, a special Mersenne prime testing algorithm was used (GIMPS, who found your prime, uses the Lucas-Lehmer test, after checking small factors explicitly). And given a completely arbitrary number of the same size, checking its primality is a lot more work, and not really feasible with current technology as far as I'm aware.
-
1$\begingroup$ Lucas-Lehmer, and a search for small factors: mersenne.org/various/math.php $\endgroup$ Feb 28, 2020 at 7:09
-
1$\begingroup$ What about the AKS primality test? It's been a while since I was following these topics, not sure about the drawbacks. $\endgroup$ Feb 28, 2020 at 15:40
-
$\begingroup$ @MargaretBloom: The AKS primality test is important theoretically, but no-one uses it in practice because it would be incredibly slow. (Its time complexity is polynomial in the number of bits, and e.g. ECPP is not known to be, but the latter is orders of magnitude faster for any input you'd care to try.) $\endgroup$ Feb 28, 2020 at 17:18
-
$\begingroup$ @MargaretBloom: Or comparing AKS, $O(\log(n)^6)$, to APR, $\log(n)^{O(\log\log\log n)}$, $n$ would have to be at least 2^2^2^6—a number with quintillions of bits—before AKS catches up. $\endgroup$ Feb 28, 2020 at 17:36
In practice (when encrypting, for example) we use probabilistic prime testing algorithms like the Miller Rabin test whose probability of failing falls off exponentially with the running time. This means we can be fairly certain a number is prime or not if we run it for a reasonable amount of time.
On the other hand, as you mentioned, primes of record breaking sizes are usually generating from special families which have ad hoc primality tests (like Mersenne primes)
-
3$\begingroup$ However, when using probobilistic method there's still a non-zero probability that the method yields false result. $\endgroup$– skykingFeb 28, 2020 at 7:10
-
3$\begingroup$ @skyking: That would make a cool, concise paper : "BTW,
2**bazillion - 1
was thought to be a prime number, but it's actuallyp * q
. kthxbye" $\endgroup$ Feb 28, 2020 at 15:49 -
1$\begingroup$ @EricDuminil en.wikipedia.org/wiki/Frank_Nelson_Cole His entirely silent chalkboard presentation was that $2^{67}-1 = 193,707,721 * 761,838,257,287$ (it was known to be composite, so not quite what you mentioned, but no one knew the factors). $\endgroup$– TeepeemmFeb 28, 2020 at 17:34
-
$\begingroup$ Sure, probabilistic tests are not a proof of primality (which is why you cannot use them to generate record breaking primes -- the community will not accept these tests as proof). However, they provide pretty good guarantees for practical applications. $\endgroup$– GerardFeb 28, 2020 at 20:02
-
1$\begingroup$ Also, as an example, for the Miller Rabin test the probability of being wrong is lower than $2^{-t}$ where t is roughly equivalent to running time. Even for t=100 this is highly highly improbable. $\endgroup$– GerardFeb 28, 2020 at 20:04
After the famous 'primes is in P' paper, there are polynomial time algorithms for testing whether a number is prime. According to wikipedia the run time of these is $O(\log(n)^6)$ and while this is massively faster than actually factoring a number like $ 2^{82,589,933}−1$ the 6th power is still too big to make this feasible on modern computers. On the other hand, these algorithms should be sufficient to quickly check that the large numbers in RSA are not prime (which is not useful for breaking RSA, the algorithms is based on the fact that the number is product of two large prime factors).
Mersenne numbers are special as others have pointed out (the proof of primality is done with the Lucas-Lehmer Test). Fermat numbers are also special and can be proven prime with Pepin's Test. There are also well known primality tests to use for numbers of the form $k2^n±1$ when $k<2^n$ (Proth's Theorem for the plus side, and a related test for the minus side using Lucas Sequences). I recommend reading from here if you are interested in these tests.
RSA-primes on the other hand don't use deterministic primality tests like the ones above. Instead (in most cases), one uses probabilistic tests (they work well in practice, but cannot prove that a number is actually prime). Such tests include Fermat test, Miller-Rabin, Euler-Jacobi, BPSW, Frobenius, etc.
If provable primes are desired, it is possible to prove RSA-primes 'prime', but will come at a timely cost (300-700 digits roughly speaking). The quickest of methods that are used include APR-CL and ECPP. Still, these become impractical (timewise) once the size of the input is about 10k or 50k digits or so, thus there is no current (practical) method to prove such large numbers primes and we must either resort to probable primes (any number), or provable primes which rely on (some) factorization of usually either $n-1$, $n+1$ or both.
Apart from the arguments mentioned in the others' answers, one more thing should be said. The GIMPS is a distributed computing project. At the moment, its performance is over 1 000 TFLOPs per second. That's a huge computing power, comparable to large supercomputers. Except the Lucas-Lehmer test (LLT), they also perform factoring and probable prime testing. Only a small fraction of candidates are subject to LLT. Even so, for the vast majority of composite numbers, their factorization is unknown. This is the main reason why they can check such large numbers.