mersenneforum.org Amazing 6
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-05, 06:46 #1 paulunderwood     Sep 2002 Database er0rr 3,491 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

23×11×43 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

3,491 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 3,491 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 593810 Posts Would you post your script?
2019-02-06, 03:45   #6
paulunderwood

Sep 2002
Database er0rr

3,491 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 1110110010002 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

3,491 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

23·11·43 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

3,491 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

3,491 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, 95 views)

 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 02:57.

Wed Nov 25 02:57:35 UTC 2020 up 76 days, 8 mins, 4 users, load averages: 1.71, 1.37, 1.31