Well, I need this for my
public key cryptography node.
A prime number (p) will always satisfy the following
congruency.
a^p%p=a (%=mod, 5%2 means the remainder of 2 divided into 5 - in this case 1)
Say, a = 2.
2^53%53 = 2 if 53 is prime.
An easy way to calculate this (used on the node above too) is to make the following chart.
(apologies for labeling of left side. 2^16!=44^2 - I really was trying to say that 2^16%53 = 44^2%53 = 28)
2^n | n | %53
----------------
2 | 1 | 2
4 | 2 | 4
16 | 4 | 16
256 | 8 | 44
44^2| 16 | 28
28^2| 32 | 42
What made this chart easy to fill out is that we calculated, say, 2^16 % 53 by squaring the answer from 2^8
We can do this since we know that 53 fits into 2^8 with 44 left over. So it must fit into 2^8*2^8 with 44^2 left over, 2^8*2^8*2^8 with at least 44^3 left over.
(2^8)^2=2^16
so 2^16%53 = (44)^2%53, which is a number that a calculator, or a patient human, can easily handle.
Using the replacement idea above, it is possible to change 2^53%53 into 2^32*2^16*2^4*2^1%53 since that equals 2^(1+4+16+32)%53.
We replace the mod values from the chart...
42*28*16*2%53
37632%53 = 2
The pseudoprime test comes from the fact that if you pick a number and check to see if the above
congruency is true, if it is, then it is very probable (but not certain!) that the number is prime.
Say, testing 2^101%101 to see if it equals 2.
Or, 3^101%101 to see if it equals 3.
The more bases it passes, the more likely the number is prime,
however if a number fails for any base (bases in this example, 2 and 3) then it is not prime.
There are some very rare numbers, however, which will pass the test no matter which base you pick.
These are known as
Carmichael numbers, there is a lovely theorem to determine them, unfortunately it requires factoring the number you are testing, which defeats the whole point of the pseudoprime test, which is fast location of large primes - usually for
public key encryption.
The Carmichael numbers under 100,000 are 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361. Note that this is much much smaller then the number of primes under 100,000 (9,592 total)
The
Miller test does not have this failing, and is has a much higher probability of accuracy in general.