2

When I say large numbers I mean large like 512 (or potentially 1024 or 2048) significant bits. These numbers are so large that there are a multitude complications. For example with python, which supports arbitrarily large integers, checking remainders up to the square root of a number so large would take by my calculation a 60+ digit number of years. Even the superior performance of a language like go only shaves a few digits of this immense runtime, and go's built-in data types don't even include integers that large. Even if all the (2-3 billion) computers in the world were working together to prove a number was prime it would still take a 50 digit (or so) number of years to prove a single 512 bit prime.

None the less the security industry appears to have a copious supply of large primes numbers at their disposal for cryptographic applications, and the largest known prime number is 2^77,232,917-1 which just seems obscene.

How could the primality of such large numbers ever practically be proven?

kpie
  • 105
  • 5
    This is, obviously, a very broad question. I suggest starting with a basic survey. – lulu Feb 18 '22 at 17:45
  • 1
    As the excellent answer below shows, you need no trial division to decide whether a given number is prime. To factor it is much more difficult, but even here we have methods far better than trial division to find a nontrivial factor. Best methods are ECM (elliptic curve method) and SIQS (self-initializing quadratic sieve) – Peter Feb 20 '22 at 10:21
  • In fact trial division is so slow that computational power would soon be utterly useless , if we would be dependent on this approach. – Peter Feb 20 '22 at 10:23

1 Answers1

3

This question is a bit too open ended but what you are overlooking is that primality is not only provable by the naive method of checking for factors.

For example, the method used for the prime $2^{77,232,917}-1$ is called the Lucas Lehmer Test. In fact there is an even large such prime known today via the same test.

This requires modular arithmetic, some group theory, and clever tricks to prove. Basically, primes $p$ form larger multiplicative groups $(\mathbb{Z}/p\mathbb{Z})^\times$ than composite numbers $c$ with $(\mathbb{Z}/c\mathbb{Z})^\times$. You can find out more about this via Euler's Totient Function. By testing multiplicative orders of elements of the group $(\mathbb{Z}/N\mathbb{Z})^\times$, one can bound the size of the group, and thus test the primality of $N$. These types of tests, called Lucasian tests, usually take $O(\log^2 N)$ time. The naive method you mentioned takes $O(\sqrt{N})$ time: a massive difference.

For the Lucas Lehmer Test, one uses a slightly different ring: $(\mathbb{Z}/N\mathbb{Z})[X]/(f)$ for some irreducible quadratic polynomial. The method is still $O(\log^2 N)$ and the specific ring chosen ensures the multiplicative group associated to the ring has size divisible by (for the example of $2^{77,232,917}-1$) $2^{77,232,917}$. The size being made up of known small factors allows us to deterministically (and heuristically) implement the algorithm well.

Tejas Rao
  • 1,890
  • I appreciate this but I am looking for an answer that is more general and not limited to Mersenne numbers. – kpie Feb 18 '22 at 18:01
  • 1
    Elliptic Curve Primality Proving is our best heuristic general method. It works much in the same way, except the group used is the group of rational points on an elliptic curve. Choosing the right curve is the hard part, and thus runs in $O(\log^4 N)$ or $O(\log^5 N)$ heuristic time. – Tejas Rao Feb 18 '22 at 18:04
  • Continuing on from this, the 'largest' primes you mentioned above simply cannot yet and have not yet been proven via ECPP or any general method. It would take too long. The largest general ECPP primes are about 40,000 digits. For the millions of digits one needs the $O(\log^2 N)$ methods for specific forms of primes mentioned above, or variants of them that don't work in general – Tejas Rao Feb 18 '22 at 18:05
  • For other $O(\log^2 N)$ heuristic tests that are specific to certain forms of numbers, see Pocklington's Test and Lenstra's Test, which again operate on a similar principle. – Tejas Rao Feb 18 '22 at 18:07
  • 2
    +1. It's worth adding that probable prime tests (Fermat, Miller-Rabin, etc.) are good enough for most real-world applications. These are essentially as fast as Lucas-Lehmer, Pocklington, etc.--practical for numbers with millions of digits, nearly instantaneous for cryptographic-sized numbers--but aren't limited to numbers of special forms, and they always return either "composite" or "almost certainly prime". – Ravi Fernando Feb 18 '22 at 21:10
  • 1
    APR (Adleman Pomerance Rumely) seems to be faster (at least on PARI/GP) , together with ECPP (elliptic curve primality proving) it is the best algorithm if we want to be 100% sure that we actually have a prime. The BPSW-test is much faster and extremely powerful (NO counterexample is known). As in most primality tests , the result "composite" is always correct. – Peter Feb 20 '22 at 10:16