Is there any way to decipher, manually of course, whether a (large enough) number is a prime?
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:
- trial division and
- Fermat's test.
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.]
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.