mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-03-11, 16:09   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×163 Posts
Post 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?
carpetpool is offline   Reply With Quote
Old 2018-03-12, 05:37   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,677 Posts
Default

This is a 3-Euler-Jacobi PRP test. See this wiki page.
paulunderwood is offline   Reply With Quote
Old 2018-03-12, 17:38   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

29×157 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2018-03-13, 02:09   #4
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5068 Posts
Post

Quote:
Originally Posted by Dr Sardonicus View Post
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.
carpetpool is offline   Reply With Quote
Old 2018-03-13, 04:02   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2018-03-13, 13:37   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

29×157 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
quadratic residues zippy Math 6 2015-07-20 13:09
quadratic composite test paulunderwood Math 90 2012-05-06 21:39
Quadratic residue mod 2^p-1 alpertron Miscellaneous Math 17 2012-04-30 15:28
Quadratic Residues Romulas Math 3 2010-05-09 03:27
NFS and quadratic characters 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.