 mersenneforum.org Amazing 6
 Register FAQ Search Today's Posts Mark Forums Read  2019-02-05, 06:46 #1 paulunderwood   Sep 2002 Database er0rr 5·701 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

F3616 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

5·701 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 5·701 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×33×5×11 Posts Would you post your script?   2019-02-06, 03:45   #6
paulunderwood

Sep 2002
Database er0rr

5×701 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 2×3×11×59 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

5·701 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

2·3·11·59 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

5×701 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

5×701 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, 97 views)   Thread Tools Show Printable Version Email this Page 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 13:50.

Fri Dec 4 13:50:21 UTC 2020 up 1 day, 10:01, 0 users, load averages: 2.83, 2.46, 2.30