mersenneforum.org Amazing 6
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-05, 06:46 #1 paulunderwood     Sep 2002 Database er0rr 481110 Posts Amazing 6 Given non-square odd candidate prime n and b=6 and any r so that a=b^r, where kronecker(a^2-4,n)==-1 and gcd(a^3-a,n)==1. then the test (b*x)^((n+1)/2) == b*kronecker(b*(a+2)) (mod n, x^2-a*x+1) implies n is prime! Proof? Counterexample? A strong test?
2019-02-05, 13:41   #2
Dr Sardonicus

Feb 2017
Nowhere

3·7·311 Posts

Quote:
 Originally Posted by paulunderwood Given non-square odd candidate prime n and b=6 and any r so that a=b^r, where kronecker(a^2-4,n)==-1 and gcd(a^3-a,n)==1. then the test (b*x)^((n+1)/2) == b*kronecker(b*(a+2)) (mod n, x^2-a*x+1) implies n is prime! Proof? Counterexample? A strong test?
Did you mean kronecker(b*(a+2),n)?

2019-02-05, 15:32   #3
paulunderwood

Sep 2002
Database er0rr

17×283 Posts

Quote:
 Originally Posted by Dr Sardonicus Did you mean kronecker(b*(a+2),n)?
Yes.

My testing with Pari/GP, using znorder(Mod(6,n)) in the script, has reached 3*10^10 without a counterexample,

 2019-02-05, 23:21 #4 paulunderwood     Sep 2002 Database er0rr 481110 Posts Since I stipulate that gcd(a^3-a,n)==1, I may as well say gcd(210,n)==1, since 6 divides a, 5 divides 6^r-1 for all r and 7 divides 6^r+1 for all r. Testing has now reached 5*10^10
 2019-02-06, 03:19 #5 CRGreathouse     Aug 2006 22·3·499 Posts Would you post your script?
2019-02-06, 03:45   #6
paulunderwood

Sep 2002
Database er0rr

17×283 Posts

Quote:
 Originally Posted by CRGreathouse Would you post your script?
Sure. Here you go. It needs some enhancements and formatting :

Code:
b=6;forstep(n=1,10000000000000,2,if(n%10000000==1,print(">>"n));if(!ispseudoprime(n)&&!issquare(n)&&Mod(b,n)^(n-1)==1,z=znorder(Mod(b,n));for(r=0,z,a=lift(Mod(b,n)^r);if(gcd(a^3-a,n)==1&&kronecker(a^2-4,n)==-1&&Mod(Mod(1,n)*b*x,x^2-a*x+1)^((n+1)/2)==b*kronecker(b*(a+2),n),print([n,r,a])))))

Last fiddled with by paulunderwood on 2019-02-06 at 03:48

 2019-02-06, 13:34 #7 Dr Sardonicus     Feb 2017 Nowhere 3·7·311 Posts Fascinating. Assuming this is a property possessed by all primes p satisfying the conditions, it implies that if kronecker(a^2 - 4, p) = -1, then lift(Mod(x,x^2 - Mod(a,p)*x + 1)^((p+1)/2))) == kronecker(a+2, p). I'm convinced that this is true, but I don't see why it's true. What is clear to me is, it's either kronecker(a+2,p) or kronecker(a-2, p). I'm probably overlooking something obvious...
2019-02-06, 14:02   #8
paulunderwood

Sep 2002
Database er0rr

481110 Posts

Quote:
 Originally Posted by Dr Sardonicus Fascinating. Assuming this is a property possessed by all primes p satisfying the conditions, it implies that if kronecker(a^2 - 4, p) = -1, then lift(Mod(x,x^2 - Mod(a,p)*x + 1)^((p+1)/2))) == kronecker(a+2, p). I'm convinced that this is true, but I don't see why it's true. What is clear to me is, it's either kronecker(a+2,p) or kronecker(a-2, p). I'm probably overlooking something obvious...
Please see the beginning of section 6 of this

2019-02-06, 14:13   #9
Dr Sardonicus

Feb 2017
Nowhere

146038 Posts

Quote:
 Originally Posted by paulunderwood Please see the beginning of section 6 of this
Thanks! The wall was starting to buckle, and my head was beginning to hurt. Hmm... I guess it isn't completely obvious...

2019-02-12, 06:32   #10
paulunderwood

Sep 2002
Database er0rr

481110 Posts

Quote:
 Originally Posted by paulunderwood Since I stipulate that gcd(a^3-a,n)==1, I may as well say gcd(210,n)==1, since 6 divides a, 5 divides 6^r-1 for all r and 7 divides 6^r+1 for all r.
Oops. 7 does not divide 6^r+1 for all r. However, 7 does divide 6^(2*r)-1 i.e. a^2-1 which divides a^3-a

2019-02-15, 05:22   #11
paulunderwood

Sep 2002
Database er0rr

17·283 Posts

Testing has reached 2*10^11 with Pari/GP, having now switched over to the much quicker attached GMP script.
Attached Files
 6_r.c (3.2 KB, 285 views)

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly Astronomy 6 2018-02-01 05:40 Miszka Information & Answers 2 2014-07-04 17:11 Xyzzy Lounge 6 2012-03-25 22:57 R.D. Silverman Factoring 5 2006-01-26 09:14 clowns789 Hardware 1 2003-12-27 16:57

All times are UTC. The time now is 15:40.

Sun Oct 1 15:40:37 UTC 2023 up 18 days, 13:22, 0 users, load averages: 1.14, 0.76, 0.77

Powered by vBulletin® Version 3.8.11
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.

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