In the introduction part of "Rational Points on Elliptic Curves", it was mentioned that there are very quick ways to check that an integer is itself a prime although it is virtually impossible to perform a factorization. And I'm curious how to quickly determine whether a large number is prime.

  • 2
    $\begingroup$ AKS primality test is a polynomial-time algorithm. There are effectively faster methods, but on the theoretical aspect I think it's considered the fastest. $\endgroup$ – barak manos Aug 23 '15 at 17:22
  • 2
    $\begingroup$ Seems like a good place to start: en.m.wikipedia.org/wiki/Primality_test $\endgroup$ – rywit Aug 23 '15 at 17:25
  • $\begingroup$ My favorite is the APR-Test (Adleman-Pomerance-Rumely-Test), but the simple strong pseudoprime test is already very powerful, but the result "prime" is not absolutely surely true. $\endgroup$ – Peter Aug 23 '15 at 18:10
  • $\begingroup$ The Elliptic curve method (ECM) is both useful to prove the primality of a number and finding prime factors upto $30-40$ digits, with much effort (or much good luck) even upto $50-60$ digit-factors. $\endgroup$ – Peter Aug 23 '15 at 18:12

Primality is a much easier problem than factorization in practice, and the best known complexity results are better as well.

As rywit mentioned, the Wikipedia page has lots of good information.

From a practical point of view, this graph gives an examples of times for single threaded implementations of a few primality proof methods on a 4770K, as well as BPSW, a fast probable prime test. It doesn't cross 1 second for average time to prove primality on random primes until ~250 digits using either APR-CL or ECPP. BPSW is still under 0.2 seconds at 2000 digits, albeit a probable prime test. The time for BPSW is 2.5-3x the cost of a single Miller-Rabin test.

Easiest way to test: use Pari/GP and its ispseudoprime function for probable prime test (using AES BPSW) or isprime function for an APR-CL proof. Other useful software includes OpenPFGW, Primo, ecpp-dj, mpz_aprcl, Wolfram Alpha, and others.

Algorithms include:

  • various methods for special forms (e.g. Mersenne, Proth, 2^n +/- 1, etc.). Some software with at least one of these include OpenPFGW, prime95, LLR, Perl/ntheory, and more.
  • ECPP. The fastest method in common use for large inputs. Primo is the standard, especially for >2k digits. There are a couple others you can find, including my ecpp-dj open source software. These give certificates of primality, which is a big advantage over other methods. This means anyone can independently and quickly verify that it passes all the necessary tests.
  • APR-CL. Pari/GP, mpz_aprcl, and alpertron are some implementations.
  • BLS75 methods. From the seminal 1975 paper, this shows numerous ways to prove primality based on partial factoring. Pocklington's test from 1914 is a simple form of this type of test.
  • AKS. Landmark theoretical result. Quite slow in practice, so isn't normally used. IMO the probability of a programming error in an AKS implementation is higher than the chances a composite will pass a well designed and implemented probable prime test.
  • Trial division. Doesn't scale.
  • Probable prime tests, such as BPSW and running random-base Miller-Rabin tests. These aren't proofs, but done well they're good enough for almost all purposes, and they're very fast. Most proof code starts with a probable prime test of some sort so it can quickly give an answer for almost every composite input.

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.