Take the 2-minute tour ×
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.

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

share|improve this question
1  
Manually, or mechanically? :-) –  Srivatsan Sep 5 '11 at 3:06
add comment

2 Answers

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.

share|improve this answer
3  
"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
2  
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
add comment

http://en.wikipedia.org/wiki/Primality_test

share|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
add comment

Your Answer

 
discard

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.