mersenneforum.org Quadratic PRP test
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-03-11, 16:09 #1 carpetpool     "Sam" Nov 2016 5·67 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 2·33·83 Posts This is a 3-Euler-Jacobi PRP test. See this wiki page.
 2018-03-12, 17:38 #3 Dr Sardonicus     Feb 2017 Nowhere 2×33×5×23 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

14F16 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 5,987 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 2×33×5×23 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

 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 04:39.

Sat Jan 28 04:39:30 UTC 2023 up 163 days, 2:08, 0 users, load averages: 1.10, 1.06, 1.00

Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔