Solovay–Strassen primality test

Solovay–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.

Concepts

Euler proved that for an odd prime number "p" and any integer "a",

:a^{(p-1)/2} equiv left(frac{a}{p} ight) pmod p

where

:left(frac{a}{p} ight)

is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to

:left(frac{a}{n} ight)

where "n" can be any odd integer. The Jacobi symbol can be computed in time O((log "n")²) using Jacobi's generalization of
law of quadratic reciprocity.

Given an odd number "n" we can contemplate whether or not the congruence

: a^{(n-1)/2} equiv left(frac{a}{n} ight) pmod n

holds for various values of the "base" "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 base "a" an "Euler witness" for "n" 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".For every composite odd "n" at least half of all bases

:a in (mathbb{Z}/nmathbb{Z})^*

are (Euler) witnesses: this contrasts with the Fermat primality test, for which the proportion of witnesses may be much smaller. 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 mathcal O(k imes log^3 n), where "k" is the number of "rounds", that is random choices of base "a", and "n" is the value we want to test for primality.

It is possible for the algorithm to "fail", that is, return an incorrect answer. If the input "n" is indeed prime, then the output will always correctly be "probably prime". However, if the input "n" is composite then it is possible for the output to be incorrectly "probably prime". The probability of failure is at most 2−"k". For purposes of cryptography if we pick a sufficiently large value of "k", such as 100, the chance of the algorithm failing in this way is so small that we can use the prime in cryptographic applications without worrying.

Average-case behaviour

The bound 1/2 on the error probability of a single round of the Solovay–Strassen test holds for any input "n", but those numbers "n" for which the bound is (approximately) attained are extremely rare. On the average, the error probability of the algorithm is significantly smaller: it is less than

: 2^{-k}expleft(-(1+o(1))frac{log x,logloglog x}{loglog x} ight)

for "k" rounds of the test, applied to uniformly random nowrap|"n" ≤ "x". [cite journal | author=P. Erdős | authorlink= | coauthors=C. Pomerance | title=On the number of false witnesses for a composite number | journal=Mathematics of Computation |volume=46 | year=1986 | issue=173 | pages=259–279 | doi=10.2307/2008231] [cite journal | author=I. Damgård | coauthors=P. Landrock, C. Pomerance | title=Average case error estimates for the strong probable prime test | journal=Mathematics of Computation | volume=61 | year=1993 | issue=203 | pages=177–194 | doi=10.2307/2152945] The same bound also applies to the related problem of what is the conditional probability of "n" being composite for a random number nowrap|"n" ≤ "x" which has been declared prime in "k" rounds of the test.

Complexity

The Solovay–Strassen algorithm shows that the decision problem COMPOSITE is in the complexity class RP [cite book | author=R. Motwani | coauthors=P. Raghavan | title=Randomized Algorithms | publisher=Cambridge University Press | year=1995 | isbn=0-521-47465-5 | pages=417-423 ] .

References

*cite journal|author=Robert M. Solovay | coauthors=Volker Strassen|journal=SIAM Journal on Computing|title=A fast Monte-Carlo test for primality|volume=6|year=1977|issue=1|pages=84–85|doi=10.1137/0206006
* 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


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia

  • Miller–Rabin primality test — The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version …   Wikipedia

  • AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… …   Wikipedia

  • Fermat primality test — The Fermat primality test is a probabilistic test to determine if a number is probably prime. ConceptFermat s little theorem states that if p is prime and 1 le a < p, then :a^{p 1} equiv 1 pmod{p}If we want to test if p is prime, then we can pick …   Wikipedia

  • Robert M. Solovay — Robert Martin Solovay (1938 ndash; ) is a set theorist who spent many years as a professor at UC Berkeley. Among his most noted accomplishments are showing (relative to the existence of an inaccessible cardinal) that the statement every set of… …   Wikipedia

  • Volker Strassen — is a German mathematician. He received in 2003, with three others, the Paris Kanellakis Award of the ACM, for the Solovay Strassen primality test.In 1971 Strassen published a paper together with Arnold Schönhage on asymptotically fastinteger… …   Wikipedia

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Volker Strassen — (2009) Volker Strassen (* 29. April 1936 in Düsseldorf Gerresheim) ist ein deutscher Mathematiker. Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • Robert M. Solovay — Robert Solovay. Robert Martin Solovay est un mathématicien américain qui a travaillé en théorie des ensembles. Il a passé de nombreuses années en tant que professeur à l université de Californie à Berkeley. Parmi ses travaux les plus importants,… …   Wikipédia en Français

  • Robert Solovay — en 1972 Robert Martin Solovay est un mathématicien américain qui a travaillé en théorie des ensembles. Il a passé de nombreuses années en tant que professeur à l université de Californie à Berkeley. Parmi ses travaux les plus importants, on… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”