display | more...
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.
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.
pseudo- = P = pseudosuit

pseudoprime n.

A backgammon prime (six consecutive occupied points) with one point missing. This term is an esoteric pun derived from number theory: a number that passes a certain kind of "primality test" may be called a `pseudoprime' (all primes pass any such test, but so do some composite numbers), and any number that passes several is, in some sense, almost certainly prime. The hacker backgammon usage stems from the idea that a pseudoprime is almost as good as a prime: it will do the same job unless you are unlucky.

--The Jargon File version 4.3.1, ed. ESR, autonoded by rescdsk.

Log in or register to write something here or to contact authors.