Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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 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 ('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.

share|cite|improve this answer
"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. 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 – Douglas S. Stones Dec 2 '10 at 12:29

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.