# How do you determine if a number is prime or composite?

Is there any way to decipher, manually of course, whether a (large enough) number is a prime?

• Manually, or mechanically? :-) – Srivatsan Sep 5 '11 at 3:06

If someone gives you a random large number, the last thing you want to do is perform a deterministic primality test -- it's very likely to be composite. Firstly, you should perform:

These can be performed using PFGW (from http://tech.groups.yahoo.com/group/primeform/). You might even want to perform a stronger pseudo-primality test.

Once these tests have been passed, then you should be somewhat confident you have a prime. If you're happy with a probable prime, then you can stop. Otherwise, you'll need a proof. [Curiously, if sufficiently many probabilistic primality tests have been performed, the probability that the number is composite can be less than the probability of a random error occurring in a "proof" of its primality.]

If your number has no particularly special form you can exploit, then your best hope is elliptic curve primality proving (see here for ECPP records). You could use Primo or Alpertron.

However, if your candidate prime happens to have a special form, then there are various deterministic primality proofs you could use. For example, the Lucas-Lehmer test (cf. GIMPS), Proth's test (http://en.wikipedia.org/wiki/Proth's_theorem), Lucas-Lehmer-Riesel test. In fact, these tests are great if you're the type of person who aspires to finding a top-5000 prime (something I used to do: see my profile).

Again, before using these tests, you should perform trial division. If you're looking for primes that can be proved by the latter two tests, you will probably find NewPGen invaluable.

• "If someone gives you a random large number, the last thing you want to do is perform a deterministic primality test -- it's very likely to be composite." - Heh. :D +1! @Sachindra: without a computer to assist, it might take you quite a while to verify if some random large number you were given is prime! – J. M. isn't a mathematician Dec 2 '10 at 12:22
• Hehe, I was tempted to mention that proving primality "manually" would be quite difficult. Re: $2^{127}-1$ "This may stand forever as the largest prime number proven by hand." (see en.wikipedia.org/wiki/%C3%89douard_Lucas). – Douglas S. Stones Dec 2 '10 at 12:29
• i guess this wasnt I was looking for. I f someone gives you a number large enough randomly and ask u to find out if it is a prime, how would u do that? – Sachindra Nov 1 '10 at 6:05