20180311, 16:09  #1 
"Sam"
Nov 2016
2×163 Posts 
Quadratic PRP test
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^((p1)/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^((q1)/2) = 1 (mod q) q = 5 or 7 modulo 12, then 3^((q1)/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 nonresidue 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? 
20180312, 05:37  #2 
Sep 2002
Database er0rr
3,677 Posts 
This is a 3EulerJacobi PRP test. See this wiki page.

20180312, 17:38  #3 
Feb 2017
Nowhere
29×157 Posts 
When Mod(a,p)^(p1) = Mod(1,p) I suggest RabinMiller.
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(p1,p) == Mod(1,p). If the first result that isn't Mod(1, p) also isn't Mod(p1,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 Last fiddled with by Dr Sardonicus on 20180312 at 17:50 Reason: Fixing typos 
20180313, 02:09  #4  
"Sam"
Nov 2016
506_{8} Posts 
Quote:
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. 

20180313, 04:02  #5 
Aug 2006
3^{2}×5×7×19 Posts 
Tailmatching in MR can give a factorization like Shor's algorithm, but the only step they'd have in common is the gcd itself  the QFT periodfinding has no analogue in MR.

20180313, 13:37  #6 
Feb 2017
Nowhere
29×157 Posts 
Regarding RabinMiller, 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. RabinMiller Primality Test: Composite Numbers Which Pass It

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
quadratic residues  zippy  Math  6  20150720 13:09 
quadratic composite test  paulunderwood  Math  90  20120506 21:39 
Quadratic residue mod 2^p1  alpertron  Miscellaneous Math  17  20120430 15:28 
Quadratic Residues  Romulas  Math  3  20100509 03:27 
NFS and quadratic characters  jasonp  Factoring  8  20060805 21:06 