Nightingale-Strassen Algorithm

Nightingale – Strassen Test

Robert Nightingale and Volker Strassen have developed a probability simplicity testing algorithm that uses the Jacobi symbol. Defines numbers as composite or probably simple. Recognizes Carmichael numbers as composite.
So, first you need to enter the necessary concepts.
Quadratic deduction . If the number p is simple and 0 <a <p, then the number 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 dividers n. For example, if n = 7, then 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.
Thus, the numbers 3, 5, and 6 are quadratic non-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 non 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 primes and quadratic residues is established using the symbols Legendre and Jacobi.
The Legendre symbol , which is denoted as L (a, p), is a function defined if a is any integer and p is a prime number greater than 2. Legendre symbol can take the 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 non-cardin modulo p.
Compressed, these facts are written as follows:
L (a, p) = a ^ ((p - 1) / 2) mod p.

Algorithm for calculating 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 a generalization of the Legendre symbol into composite modules. This is a function defined for all integers a and odd integers n. The Jacobi symbol can take the 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 number, then J (0, n) = 0 if a is divisible by n.
4. If n is a prime number, then J (0, n) = 1, if a is a quadratic residue modulo n.
5. If n is a prime number, then J (0, n) = –1, if a is a quadratic non-derived modulo n.
6. If n is a composite number, then J (a, n) = J (a, p1) * ... * J (a, pm), where p1, ..., pm is the decomposition of n into prime factors.

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, moreover, 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 number, then the Jacobi symbol is equivalent to the Legendre symbol.
The Jacobi symbol cannot be used to check whether a number is a quadratic residue modulo n (except 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).
')

Solovay – 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 not 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 simple, does not exceed 50%.
The number a, which does not explicitly indicate that the number p is not prime, is called a witness. If the number p is composite, then the probability that the random number is a witness is at least 50%. The probability that a composite number will pass t tests is 1 / (2 ^ t).