Quadratic PRP test

[carpetpool]

Let p be a prime and a an integer. If m = p (mod a) and by quadratic reciprocity, every prime q congruent to m modulo a, a is a quadratic residue modulo q, then a^((p-1)/2) = 1 (mod p), else it is congruent to -1 (mod p). If p fails this test, then it is composite.

Example:

p = 2465
a = 3

Here we see that for every prime q congruent to 1 or 11 modulo 12, 3 is a quadratic residue modulo q. This implies that if

q = 1 or 11 modulo 12, then 3^((q-1)/2) = 1 (mod q)
q = 5 or 7 modulo 12, then 3^((q-1)/2) = -1 (mod q)

If these don't hold for the following congruence, q is not prime.

Here we see that p = 2465 modulo 12 = 5 implying that a = 3 is a quadratic non-residue modulo 2465, .

3^2464 = 1 mod 2465, so 2465 could still be prime.

3^1232 = 1 mod 2465, and by the law of quadratic reciprocity, if 2465 were prime, 3^1232 should be -1 mod 2465, not 1 mod 2465, therefore we know for sure that 2465 is composite, not prime.

2465 happens to fail the SPRP test for base 3, and is also a Carmichael number, there should be a base a such that this equivalence fails and 2465 passes the SPRP test, therefore it is not the SPRP test which would show 2465 is composite, but rather the "Quadratic Test" that shows this.

Any further thoughts on improving the test?

[paulunderwood]

This is a 3-Euler-Jacobi PRP test. See this wiki page.

[Dr Sardonicus]

When Mod(a,p)^(p-1) = Mod(1,p) I suggest Rabin-Miller.

If your number p is prime, and you keep dividing the exponent by 2, you will either reach an odd exponent and still get Mod(1, p), or you will at some point get Mod(p-1,p) == Mod(-1,p).

If the first result that isn't Mod(1, p) also isn't Mod(p-1,p), you've got a proper factorization:

Mod(3,2465)^1232 = Mod(1,2465)

Dividing the exponent by 2 again,

Mod(3,2465)^616 = Mod(1886, 2465)

gcd(1886 + 1,2465) = 17

gcd(1886 - 1,2465) = 145

[carpetpool]

Originally Posted by Dr Sardonicus

When Mod(a,p)^(p-1) = Mod(1,p) I suggest Rabin-Miller.

If your number p is prime, and you keep dividing the exponent by 2, you will either reach an odd exponent and still get Mod(1, p), or you will at some point get Mod(p-1,p) == Mod(-1,p).

If the first result that isn't Mod(1, p) also isn't Mod(p-1,p), you've got a proper factorization:

Mod(3,2465)^1232 = Mod(1,2465)

Dividing the exponent by 2 again,

Mod(3,2465)^616 = Mod(1886, 2465)

gcd(1886 + 1,2465) = 17

gcd(1886 - 1,2465) = 145

As you've pointed out already, you were explaining the Miller-Rabin (or strong PRP) test. At the end, when you mention a proper factorization of p using the residue from p^((p-1)/2^n) modulo p which isn't 1 or -1, isn't this the same as Shor's Algorithm?

Shor's algorithm would be efficient if and only if step 4 in the procedure is easy to do.

I'm not sure of how to find the smallest e in a^e = 1 modulo n for any given integer n.

[CRGreathouse]

Tail-matching in M-R can give a factorization like Shor's algorithm, but the only step they'd have in common is the gcd itself -- the QFT period-finding has no analogue in M-R.

[Dr Sardonicus]

Regarding Rabin-Miller, the following abstract might also be of interest. The page also has a link from which you can download a pdf of the paper itself. Rabin-Miller Primality Test: Composite Numbers Which Pass It