6.10 How to Test Whether a Number is a Prime? 1176.10 How to Test Whether a Number is a Prime?.........
Is 123,456 a prime? Of course not, it is even. Is 1,234,567 a prime? This is
not so easy to answer, but if you are hard pressed, you can try all numbers
2 , 3 , 4 , 5 ...to see if they are divisors. If you have the patience to go up to
127, then you are done: 1234567 = 127·9721.
What about 1,234,577? Again you can try to find a divisor by trying
out 2, 3 , 4 , 5 ,.... But this time you don’t find a proper divisor! Still, if you
are really patient and keep on until you get to the square root of 1234577,
which is 1111. 1 ..., you know that you are not going to find a proper divisor
(why?).
Now what about the number
1 , 111 , 222 , 233 , 334 , 444 , 555 , 566 , 667 , 777 , 888 , 899 ,967?If this is a prime (as it is), then we have to to try out all numbers up to its
square root; since the number is larger than 10^36 , its square root is larger
than 10^18. Trying out more than 10^18 numbers is a hopeless task even for
the world’s most powerful computer.
The Fermat test.So how do we know that this number is a prime? Well,
our computer tells us, but how does the computer know? An approach is
offered by Fermat’s Theorem. Its simplest nontrivial case says thatifpis
a prime, thenp| 2 p−2. If we assume thatpis odd (which only excludes
the casep= 2), then we also know thatp| 2 p−^1 −1.
What happens if we check the divisibility relationn| 2 n−^1 −1 for com-
posite numbers? It obviously fails ifnis even (no even number is a divisor
of an odd number), so let’s restrict our attention to odd numbers. Here are
some results:
9 28 −1 = 255, 15 214 −1=16, 383 , 21 220 −1=1, 048 , 575 ,25 224 −1=16, 777 , 215.This suggests that perhaps we could test whether the numbernis a prime
by checking whether the relationn| 2 n−^1 −1 holds. This is a nice idea,
but it has several major shortcomings.
How to compute LARGE powers.It is easy to write up the formula
2 n−^1 −1, but it is quite a different matter to compute it! It seems that to
get 2n−^1 , we have to multiply by 2n−2 times. For a 100-digit numbern,
this is about 10^100 steps, which we will never be able to carry out.
But we can be tricky when we compute 2n−^1. Let us illustrate this on the
example of 2^24 : We could start with 2^3 = 8, square it to get 2^6 = 62, square
it again to get 2^12 = 4096, and square it once more to get 2^24 =16, 777 ,216.
Instead of 23 multiplications, we needed only 5.
It seems that this trick worked only because 24 was divisible by such
a large power of 2, and so we could compute 2^24 by repeated squaring,