Originally posted by XanthosNZIf you want absolute certainty then there are no short cuts, but there are probabilistic methods that can tell with a very high certainty whether or not a number is prime - and very quickly. This is important for modern public key encryption algorithms: generating two very large primes and multplying them together is easy, factorizing the result is practially impossible.
...
Other than this no shortcut exists. This makes testing extremely large numbers for primality extremely timeconsuming.
Furthermore, certain classes of number do allow for some short cuts. For instance the Mersenne Numbers, for which there is the Lucas-Lehmer test. This has been used to show that 2^30,402,457 - 1 (a 9.1 million digit number) is prime.
Originally posted by howardbradleyThe first bit will only tell you if a number is 'probably prime'. Many of the probabilistic tests are also not theorems, the Miller-Rabin primality test actually relies on the Riemann hypothesis (which as we all know is unproven).
If you want absolute certainty then there are no short cuts, but there are probabilistic methods that can tell with a very high certainty whether or not a number is prime - and very quickly. This is important for modern public key encryption algorithms: generating two very large primes and multplying them together is easy, factorizing the result is ...[text shortened]... test. This has been used to show that 2^30,402,457 - 1 (a 9.1 million digit number) is prime.
The second are called sieves. Basically you find a form of number that contains an elevated percentage of primes. Not every prime will have that form and not every number of that form will be prime but it can shorten the search for a prime number in a given range.