﻿ Solovay–Strassen primality test : definition of Solovay–Strassen primality test and synonyms of Solovay–Strassen primality test (English)
 »
Arabic Bulgarian Chinese Croatian Czech Danish Dutch English Estonian Finnish French German Greek Hebrew Hindi Hungarian Icelandic Indonesian Italian Japanese Korean Latvian Lithuanian Malagasy Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Vietnamese
Arabic Bulgarian Chinese Croatian Czech Danish Dutch English Estonian Finnish French German Greek Hebrew Hindi Hungarian Icelandic Indonesian Italian Japanese Korean Latvian Lithuanian Malagasy Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Vietnamese

# definition - Solovay–Strassen primality test

definition of Wikipedia

# 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[1] that for an odd prime number p and any integer a,

$a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p$

where $\left(\tfrac{a}{p}\right)$ is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to $\left(\tfrac{a}{n}\right)$, 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}\right) \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). This base a is called an Euler witness for n; it is a witness for the compositeness of n. The base a is called an Euler liar for n if the congruence is true while n is composite.

For every composite odd n at least half of all bases

$a \in (\mathbb{Z}/n\mathbb{Z})^*$

are (Euler) witnesses:[2] 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.

## Example

Suppose we wish to determine if n = 221 is prime. We write (n−1)/2=110.

We randomly select an a = 47 < n. We compute:

• a(n−1)/2 mod n  =  47110 mod 221  =  −1 mod 221
• $(\tfrac{a}{n})$ mod n  =  $(\tfrac{47}{221})$ mod 221  =  −1 mod 221.

This gives that, either 221 is prime, or 47 is an Euler liar for 221. We try another random a, this time choosing a = 2:

• a(n−1)/2 mod n  =  2110 mod 221  =  30 mod 221
• $(\tfrac{a}{n})$ mod n  =  $(\tfrac{2}{221})$ mod 221  =  −1 mod 221.

Hence 2 is an Euler witness for the compositeness of 221, and 47 was in fact an Euler liar. Note that this tells us nothing about the factors of 221 (which are 13 and 17).

## Algorithm and running time

The algorithm can be written in pseudocode 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 randomly in the range [2,n − 1]
x ← $\left( \tfrac{a}{n}\right)$
if x = 0 or $a^{(n-1)/2}\not\equiv x\pmod n$ 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 different values of a we test.

## Accuracy of the test

It is possible for the algorithm to 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 number n is then called a pseudoprime.

When n is odd and composite, at least half of all a with gcd(a,n) = 1 are Euler witnesses. We can prove this as follows: let {a1, a2, ..., am} be the Euler liars and a an Euler witness. Then, for i = 1,2,...,m:

$(a\cdot a_i)^{(n-1)/2}=a^{(n-1)/2}\cdot a_i^{(n-1)/2}= a^{(n-1)/2}\cdot \left(\frac{a_i}{n}\right) \not\equiv \left(\frac{a}{n}\right)\left(\frac{a_i}{n}\right)\pmod{n}.$

Because the following holds:

$\left(\frac{a}{n}\right)\left(\frac{a_i}{n}\right)=\left(\frac{a\cdot a_i}{n}\right),$

now we know that

$(a\cdot a_i)^{(n-1)/2}\not\equiv \left(\frac{a\cdot a_i}{n}\right)\pmod{n}.$

This gives that each ai gives a number a·ai, which is also an Euler witness. So each Euler liar gives an Euler witness and so the number of Euler witnesses is larger or equal to the number of Euler liars. Therefore, when n is composite, at least half of all a with gcd(a,n) = 1 is an Euler witness.

Hence, the probability of failure is at most 2k (compare this with the probability of failure for the Miller-Rabin primality test, which is at most 4k).

For purposes of cryptography the more bases a we test, i.e. if we pick a sufficiently large value of k, the better the accuracy of test. Hence the chance of the algorithm failing in this way is so small that the (pseudo) prime is used in practice in cryptographic applications, but for applications for which it is important to have a prime, a test like ECPP or Pocklington[3] should be used which proves primality.

## 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}\exp\left(-(1+o(1))\frac{\log x\,\log\log\log x}{\log\log x}\right)$

for k rounds of the test, applied to uniformly random nx.[4][5] The same bound also applies to the related problem of what is the conditional probability of n being composite for a random number nx 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.[6]

## References

1. ^ Euler's criterion
2. ^ PlanetMath
3. ^ Pocklington test on Mathworld
4. ^ P. Erdős; C. Pomerance (1986). "On the number of false witnesses for a composite number". Mathematics of Computation (American Mathematical Society) 46 (173): 259–279. DOI:10.2307/2008231. JSTOR 2008231.
5. ^ I. Damgård; P. Landrock, C. Pomerance (1993). "Average case error estimates for the strong probable prime test". Mathematics of Computation (American Mathematical Society) 61 (203): 177–194. DOI:10.2307/2152945. JSTOR 2152945.
6. ^ R. Motwani; P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. pp. 417–423. ISBN 0-521-47465-5.

• Solovay, Robert M.; Strassen, Volker (1977). "A fast Monte-Carlo test for primality". SIAM Journal on Computing 6 (1): 84–85. DOI:10.1137/0206006
• Dietzfelbinger, Martin. "Primality Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P"". Lecture Notes in Computer Science. 3000. ISBN 3-540-40344-2

sensagent's content

• definitions
• synonyms
• antonyms
• encyclopedia

Dictionary and translator for handheld

New : sensagent is now available on your handheld

sensagent's office

Shortkey or widget. Free.

Windows Shortkey: . Free.

Vista Widget : . Free.

Webmaster Solution

Alexandria

A windows (pop-into) of information (full-content of Sensagent) triggered by double-clicking any word on your webpage. Give contextual explanation and translation from your sites !

Try here  or   get the code

SensagentBox

With a SensagentBox, visitors to your site can access reliable information on over 5 million pages provided by Sensagent.com. Choose the design that fits your site.

WordGame

The English word games are:
○   Anagrams
○   Wildcard, crossword
○   Lettris
○   Boggle.

Lettris

Lettris is a curious tetris-clone game where all the bricks have the same square shape but different content. Each square carries a letter. To make squares disappear and save space for other squares you have to assemble English words (left, right, up, down) from the falling squares.

boggle

Boggle gives you 3 minutes to find as many words (3 letters or more) as you can in a grid of 16 letters. You can also try the grid of 16 letters. Letters must be adjacent and longer words score better. See if you can get into the grid Hall of Fame !

English dictionary
Main references

Most English definitions are provided by WordNet .
English thesaurus is mainly derived from The Integral Dictionary (TID).
English Encyclopedia is licensed by Wikipedia (GNU).

The wordgames anagrams, crossword, Lettris and Boggle are provided by Memodata.
The web service Alexandria is granted from Memodata for the Ebay search.
The SensagentBox are offered by sensAgent.

Translation

Change the target language to find translations.
Tips: browse the semantic fields (see From ideas to words) in two languages to learn more.

last searches on the dictionary :

2717 online visitors

computed in 0.031s

I would like to report:
section :
a spelling or a grammatical mistake
an offensive content(racist, pornographic, injurious, etc.)