# How to determine whether a large number is prime

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.

• 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. – barak manos Aug 23 '15 at 17:22
• Seems like a good place to start: en.m.wikipedia.org/wiki/Primality_test – rywit Aug 23 '15 at 17:25
• 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. – Peter Aug 23 '15 at 18:10
• 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. – Peter Aug 23 '15 at 18:12

## 1 Answer

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.