mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-02-05, 06:46   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Question 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?
paulunderwood is offline   Reply With Quote
Old 2019-02-05, 13:41   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

F3616 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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)?
Dr Sardonicus is online now   Reply With Quote
Old 2019-02-05, 15:32   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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,
paulunderwood is offline   Reply With Quote
Old 2019-02-05, 23:21   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2019-02-06, 03:19   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×33×5×11 Posts
Default

Would you post your script?
CRGreathouse is offline   Reply With Quote
Old 2019-02-06, 03:45   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-02-06, 13:34   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×11×59 Posts
Default

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...
Dr Sardonicus is online now   Reply With Quote
Old 2019-02-06, 14:02   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-02-06, 14:13   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·3·11·59 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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...
Dr Sardonicus is online now   Reply With Quote
Old 2019-02-12, 06:32   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-02-15, 05:22   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Testing has reached 2*10^11 with Pari/GP, having now switched over to the much quicker attached GMP script.
Attached Files
File Type: c 6_r.c (3.2 KB, 97 views)
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Don't miss this amazing trick that the moon is going to do! Uncwilly Astronomy 6 2018-02-01 05:40
Amazing result in P-1 Miszka Information & Answers 2 2014-07-04 17:11
Amazing academic resource Xyzzy Lounge 6 2012-03-25 22:57
Amazing!!! R.D. Silverman Factoring 5 2006-01-26 09:14
Two Amazing Things 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.