Solovey-Strassen Algorithm
Solovey – Strassen Test
Robert Nightingale and Volker Strassen have developed a probabilistic test for simplicity of a number that uses the Jacobi symbol. Defines numbers as compound or probably prime. Recognizes Carmichael numbers as compound.
So, first you need to introduce the necessary concepts.
Quadratic deduction . If p is prime and 0 <a <p, then a is a quadratic residue modulo p if there are values of x such that
x2 = a (mod p).
In order for the number a to be a quadratic residue modulo n, it must be a quadratic residue modulo all prime divisors of n. For example, if n = 7, then the quadratic residues are 1, 2, and 4.
12 = 1 = 1 mod 7,
22 = 4 = 4 mod 7,
32 = 9 = 2 mod 7,
42 = 16 = 2 mod 7,
52 = 25 = 1 mod 7,
62 = 36 = 1 mod 7.
Conversely, in the following equations there are no x values that satisfy them.
x2 = 3 mod 7,
x2 = 5 mod 7,
x2 = 6 mod 7.
So, the numbers 3, 5 and 6 are quadratic residues modulo 7.
If the number p is odd, then there are exactly (p - 1) / 2 quadratic residues modulo p and the same number of quadratic residues modulo p. If n is the product of two primes p and q, then there are exactly (p - 1) (q - 1) / 4 quadratic residues modulo n.
The relationship between prime numbers and quadratic residues is established using the Legendre and Jacobi symbols.
Legendre symbol, which is denoted as L (a, p), is a function defined if a is any integer and p is a prime greater than 2. The Legendre symbol can take values 0, 1 and –1.
L (a, p) = 0 if a is divisible by p.
L (a, p) = 1 if a is a quadratic residue modulo p,
L (a, p) = –1 if a is a quadratic residue modulo p.
Compressed, these facts are written as follows:
L (a, p) = a ^ ((p - 1) / 2) mod p.
The algorithm for computing the Legendre symbol.
1. If a = 1, then L (a, p) = 1.
2. If the number a is even, then L (a, p) = L (a / 2, p) * ((- 1) ^ ((p ^ 2-1) / 8)).
3. If the number a is odd and a! = 1, then L (a, p) = L (p mod a, a) * ((- 1) ^ ((a – 1) * (p – 1) / 4 )).
The Jacobi symbol , which is denoted as J (a, n), is the generalization of the Legendre symbol to composite modules. This is a function defined for all integers a and odd integers n. The Jacobi symbol can take values 0, 1, and –1.
The Jacobi symbol can be set as follows.
1. The Jacobi symbol is defined only for odd numbers n.
2. J (0, n) = 0.
3. If n is a prime, then J (0, n) = 0 if a is divisible by n.
4. If n is a prime, then J (0, n) = 1, if a is a quadratic residue modulo n.
5. If n is a prime, then J (0, n) = –1, if a is a quadratic non-residue modulo n.
6. If n is a composite number, then J (a, n) = J (a, p1) * ... * J (a, pm), where p1, ..., pm is the prime factorization of n.
Algorithm for computing the Jacobi symbol.
1. J (1, n) = 1.
2. J (a * b, n) = J (a, n) * J (b, n).
3. J (2, n) = 1 if (n ^ 2 - 1) / 8 is even, and –1 otherwise.
4. J (a, n) = J ((a mod m), n).
5. J (a, b1 * b2) = J (a, b1) J (a, b2).
6. If gcd (a, b) = 1 and, in addition, the numbers a and b are odd, then
6.1. J (a, b) = J (b, a) if (a - 1) * (b - 1) / 4 is an even number.
6.2. J (a, b) = –J (b, a) if (a - 1) * (b - 1) / 4 is an odd number.
If n is a prime, then the Jacobi symbol is equivalent to the Legendre symbol.
The Jacobi symbol cannot be used to check whether the number a is a quadratic residue modulo n (except for the case when the number n is prime). If J (a, n) = 1 and n is a composite number, then the number a is not always a quadratic residue:
J (7, 143) = J (7, 11) * J (7, 13) = (–1) * (- 1) = 1,
although there are no integers x such that x2 7 (mod 143).
The Solovey – Strassen Algorithm
1. Choose a random number a less than p.
2. If gcd (a, p)! = 1, then the number p is composite and the test can be continued.
3. Calculate j = a ^ ((p – 1) / 2) mod p.
4. Calculate the Jacobi symbol J (a, p).
5. If j! = J (a, p), then the number p is definitely not prime.
6. If j = J (a, p), then the probability that the number p is not prime does not exceed 50%.
The number a, which does not explicitly indicate that the number p is not prime, is called a witness. If p is a composite number, then the probability of a random number being a witness is at least 50%. The probability that a composite number passes t tests is 1 / (2 ^ t).
