 mersenneforum.org Quadratic PRP test
 Register FAQ Search Today's Posts Mark Forums Read 2018-03-11, 16:09 #1 carpetpool   "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^((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?   2018-03-12, 05:37 #2 paulunderwood   Sep 2002 Database er0rr 3,677 Posts This is a 3-Euler-Jacobi PRP test. See this wiki page.    2018-03-12, 17:38 #3 Dr Sardonicus   Feb 2017 Nowhere 29×157 Posts 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 Last fiddled with by Dr Sardonicus on 2018-03-12 at 17:50 Reason: Fixing typos   2018-03-13, 02:09   #4
carpetpool

"Sam"
Nov 2016

5068 Posts Quote:
 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.   2018-03-13, 04:02 #5 CRGreathouse   Aug 2006 32×5×7×19 Posts 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.   2018-03-13, 13:37 #6 Dr Sardonicus   Feb 2017 Nowhere 29×157 Posts 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  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post zippy Math 6 2015-07-20 13:09 paulunderwood Math 90 2012-05-06 21:39 alpertron Miscellaneous Math 17 2012-04-30 15:28 Romulas Math 3 2010-05-09 03:27 jasonp Factoring 8 2006-08-05 21:06

All times are UTC. The time now is 20:22.

Tue May 18 20:22:12 UTC 2021 up 40 days, 15:03, 0 users, load averages: 1.73, 1.87, 1.96