| cwave.eu5.org
Also see: http://www.angelfire.com/dragon/letstry cwave04 at yahoo dot com |
 Last updated on Fri May 21 11:50:25 IST 2010. |
|
The Solovay-Strassen algorithm
We shall now learn an algorithm for testing if a given number is prime or not. We can of course keep on dividing the number by all numbers less than or equal to its square root, until we find a factor. But this is a lengthy procedure and takes too long even for a computer. The Solovay-Strassen algorithm employs a faster technique. The speed is gained at the expense of accuracy: the algorithm may sometimes give a wrong result. The chance that it will give a wrong result is quite small, and so it is almost like a perfect algorithm. The algorithm is as follows. Suppose that we are to test if a given odd number n is prime or not. Then the algorithm picks any number a < n, and computes two quantities: the Jacobi symbol(a/n)and the power
a(n-1)/2 (mod n).Recall from Euler's theorem that these two quantities must be the same if n is indeed a prime. But is the converse true, i.e., if these quantities are the same can we conclude that n is a prime? Unformtunately, the answer is "No". But still, if we try out many such a's and always find that the two quantities match then we are confidence grows that n is highly likely to be a prime. This is the idea of the Solovay-Strassen algorithm: consider a lot of a's and check if the two quantities match. If there is even a single mismatch, stop and declare n as composite. If we find no mismatch declare n as prime (meaning highly likely to be a prime). What is the chance of making a mistake here (i.e., falsely identifying a composite number as prime)? The answer depends on the number of a's you have tested with. The more a's you use the less the chance of a mistake. We shall assume that the a's are chosen randomly and independently. Then it can be shown that if you test with k values of a's the chance of a mistake is less than 2-k , which is quite low even if k is just 20.
