العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolSOLOVAY-STRASSEN PRIMALITY TEST
The 'Solovay-Strassen primality test', developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or ''probably'' prime. It has been largely superseded by the Miller-Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem.
Euler proved that for a prime number ''p'' and any integer ,
:
where
:
is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to
:
where ''n'' can be any odd integer. The Jacobi symbol can be computed in time O((log ''n'')2) using Jacobi's generalization of
law of quadratic reciprocity.
We can contemplate whether or not the congruence
:
holds for various values of ''a''. If ''n'' is prime then this congruence is true for all ''a''. So if we pick values of ''a'' at random and test the congruence, then
as soon as we find an ''a'' which doesn't fit the congruence we know that ''n'' is not prime (but this does not tell us a nontrivial factorization of ''n'').
Call ''a'' an ''Euler witness'' if the above congruence with the Jacobi symbol does not hold at ''a'' -- that is to say that ''a'' is a witness for the compositeness of ''n''.
Unlike the Fermat primality test, for every composite odd ''n'' at least half of all
:
are (Euler) witnesses. Therefore, there are no (odd) composite ''n'' without lots of witnesses, unlike the case of Carmichael numbers for Fermat's test.
The algorithm can be written as follows:
:'Inputs': ''n'': a value to test for primality; ''k'': a parameter that determines the accuracy of the test
:'Output': composite if ''n'' is composite, otherwise probably prime
:repeat ''k'' times:
::choose ''a'' at random in the interval [1,''n''-1]
::''x'' ← (''a''/''n'')
::if ''x'' = 0 or ''a''(''n'' − 1)/2 mod ''n'' ≠ ''x'' then return composite
:return probably prime
Using fast algorithms for modular exponentiation, the running time of this algorithm is O(''k'' × log3''n''), where ''k'' is the number of times we test a random ''a'', and ''n'' is the value we want to test for primality. The probability of the algorithm failing is 2-''k''. For purposes of cryptography if we pick a sufficiently large value of ''k'', such as 100, the chance of the algorithm failing is so small that we can use the prime in cryptographic applications without worrying.
★ A fast Monte-Carlo test for primality, Solovay, Robert M. and Volker Strassen, , , SIAM Journal on Computing, 1977
★ Martin Dietzfelbinger, Primality Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P" (section 6), Series: Lecture Notes in Computer Science , Vol. 3000
| Contents |
| Concepts |
| Algorithm and running time |
| Reference |
Concepts
Euler proved that for a prime number ''p'' and any integer ,
:
where
:
is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to
:
where ''n'' can be any odd integer. The Jacobi symbol can be computed in time O((log ''n'')2) using Jacobi's generalization of
law of quadratic reciprocity.
We can contemplate whether or not the congruence
:
holds for various values of ''a''. If ''n'' is prime then this congruence is true for all ''a''. So if we pick values of ''a'' at random and test the congruence, then
as soon as we find an ''a'' which doesn't fit the congruence we know that ''n'' is not prime (but this does not tell us a nontrivial factorization of ''n'').
Call ''a'' an ''Euler witness'' if the above congruence with the Jacobi symbol does not hold at ''a'' -- that is to say that ''a'' is a witness for the compositeness of ''n''.
Unlike the Fermat primality test, for every composite odd ''n'' at least half of all
:
are (Euler) witnesses. Therefore, there are no (odd) composite ''n'' without lots of witnesses, unlike the case of Carmichael numbers for Fermat's test.
Algorithm and running time
The algorithm can be written as follows:
:'Inputs': ''n'': a value to test for primality; ''k'': a parameter that determines the accuracy of the test
:'Output': composite if ''n'' is composite, otherwise probably prime
:repeat ''k'' times:
::choose ''a'' at random in the interval [1,''n''-1]
::''x'' ← (''a''/''n'')
::if ''x'' = 0 or ''a''(''n'' − 1)/2 mod ''n'' ≠ ''x'' then return composite
:return probably prime
Using fast algorithms for modular exponentiation, the running time of this algorithm is O(''k'' × log3''n''), where ''k'' is the number of times we test a random ''a'', and ''n'' is the value we want to test for primality. The probability of the algorithm failing is 2-''k''. For purposes of cryptography if we pick a sufficiently large value of ''k'', such as 100, the chance of the algorithm failing is so small that we can use the prime in cryptographic applications without worrying.
Reference
★ A fast Monte-Carlo test for primality, Solovay, Robert M. and Volker Strassen, , , SIAM Journal on Computing, 1977
★ Martin Dietzfelbinger, Primality Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P" (section 6), Series: Lecture Notes in Computer Science , Vol. 3000
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
