Solovay–Strassen primality test

The Solovay -Strassen test ( according to Robert M. Solovay and Volker Strassen ) is a probabilistic primality test. The test checks for an odd number n, whether it is prime or composite. In the latter case, the test, however, is not a factor of the number n generally gives

The Solovay -Strassen test is how the Miller -Rabin test, a Monte Carlo algorithm. That is, it only provides a certain probability ( 50%) of a statement. By repeating this probability can also be enlarged. If the test ( repeated ) are not valid, so this can be as " n is probably prime " interpret.

Method

For an odd number n, which is to test for primality, a natural number a is chosen with 1

  • Calculate the Jacobi symbol J ( a, n). If n is a prime, then J ( a, n) ≡ b mod n must apply. Does not this, n can not be prime and the test is completed.
  • If the calculations sequentially g = 1, b = 1 or b = n-1, J ( a, n) ≡ b mod n result, the Solovay -Strassen test provides no statement, n, hence it may be a prime number.

Assessment

To evaluate the quality of the Solovay - Strassen test, must be distinguished whether n is prime or not.

  • If n is prime, the test always returns the correct result (ie, " No statement ").
  • If n is not a prime number, is the probability, in the first step of the assay to select an A, so that the test is a false result, less than 1/ 2 (see below: Improper tools).

To increase the power of the test for non- prime, the test with independently chosen random bases is repeated a sufficient number of times. If the test is repeated k times, then the probability that all K iterations, the result is " no information " is (although N is not a prime number ), less than. This is a pessimistic estimate - in most cases the quality will be much better.

Efficiency

The Solovay -Strassen test is efficient because the gcd, the powers and the Jacobi symbol can be computed efficiently.

Example

The example of the composite number n = 91 ( a Fermat pseudoprime to - for example - the bases 17, 29 ) is shown a possible sequence of tests:

Is 91 a prime number?

Test 1: a = 29

Test 2: a = 17

Test 3: a = 23

False witnesses

Let n > 2 is an odd composite number. Too prime number is called a false witness for the primality of respect to the Solovay - Strassen test, if

For so the bases are false witnesses. Since the amount of false witnesses is a subgroup of the multiplicative group with order less than or is equal to (where denotes the Euler φ - function that the number of prime numbers less than indicates ) and is considered, are more than half of the available range of bases false witnesses. Thus is achieved in runs a probability of an error (i.e., a compound number is not recognized as such ), which is smaller.

One is the Euler's theorem: For any prime p > 2

With this criterion, all numbers are screened out, which are neither prime nor Euler pseudo- prime to the base a.

The other property combines this with the Legendre symbol: For every prime number p> 2

Since one can not assume at the test numbers indicate that it is prime, one uses the Jacobi symbol. This criterion also the Euler -Jacobi pseudoprimes fall out.

Randomized algorithm Euler pseudoprime Jacobi-Symbol Paulo Ribenboim
737549
de