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

2019-10-26, 02:21   #23
carpetpool

"Sam"
Nov 2016

1001011002 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?
Is it possible to generalize to b = (any constant c) ? Say b = 5? Is it supposed to work for all primes p, or perhaps just those such that (a^2-4) is a quadratic residue (or non residue) mod p?

2019-10-26, 02:31   #24
paulunderwood

Sep 2002
Database er0rr

32×7×53 Posts

Quote:
 Originally Posted by carpetpool Is it possible to generalize to b = (any constant c) ? Say b = 5? Is it supposed to work for all primes p, or perhaps just those such that (a^2-4) is a quadratic residue (or non residue) mod p?
b=5 seems to work. I have not tested as deeply as b=6. Some other bases like b=2 have quite a few counterexamples to a freely ranging "r". Having (a^2-4) as a QNR is crucial.

For example:

Code:
b=2;forstep(n=3,10000000,2,if(!ispseudoprime(n)&&Mod(b,n)^(n-1)==1,a=b;r=1;while(a!=1,if(kronecker(a^2-4,n)==-1&&gcd(a^2-1,n)==1&&Mod(Mod(1,n)*b*x,x^2-a*x+1)^((n+1)/2)==b*kronecker(b*(a+2),n),print([b,n,r,a]));r++;a=(a*b)%n)))
[2, 2047, 6, 64]
[2, 42799, 11, 2048]
[2, 90751, 38, 25020]
[2, 256999, 15, 32768]
[2, 271951, 38, 170282]
[2, 514447, 90, 72499]
[2, 741751, 108, 729064]
[2, 916327, 120, 513301]
[2, 2205967, 186, 1023752]
[2, 2304167, 15, 32768]
[2, 2748023, 120, 220632]
[2, 2811271, 28, 1364711]
[2, 2953711, 23, 2481186]
[2, 2976487, 216, 271594]
[2, 4469471, 153, 2703791]
[2, 4863127, 276, 1059661]
[2, 5016191, 162, 3677584]
[2, 6334351, 182, 2259489]
[2, 6787327, 326, 440965]
[2, 7674967, 59, 3268337]
[2, 8095447, 356, 2233088]
[2, 8388607, 12, 4096]
[2, 8727391, 18, 262144]
[2, 9588151, 20, 1048576]
[2, 9995671, 23, 8388608]

Last fiddled with by paulunderwood on 2019-10-26 at 02:45

2019-10-26, 20:36   #25
carpetpool

"Sam"
Nov 2016

22×3×52 Posts

Quote:
 Originally Posted by paulunderwood b=5 seems to work. I have not tested as deeply as b=6. Some other bases like b=2 have quite a few counterexamples to a freely ranging "r". Having (a^2-4) as a QNR is crucial. For example: Code: b=2;forstep(n=3,10000000,2,if(!ispseudoprime(n)&&Mod(b,n)^(n-1)==1,a=b;r=1;while(a!=1,if(kronecker(a^2-4,n)==-1&&gcd(a^2-1,n)==1&&Mod(Mod(1,n)*b*x,x^2-a*x+1)^((n+1)/2)==b*kronecker(b*(a+2),n),print([b,n,r,a]));r++;a=(a*b)%n))) [2, 2047, 6, 64] [2, 42799, 11, 2048] [2, 90751, 38, 25020] [2, 256999, 15, 32768] [2, 271951, 38, 170282] [2, 514447, 90, 72499] [2, 741751, 108, 729064] [2, 916327, 120, 513301] [2, 2205967, 186, 1023752] [2, 2304167, 15, 32768] [2, 2748023, 120, 220632] [2, 2811271, 28, 1364711] [2, 2953711, 23, 2481186] [2, 2976487, 216, 271594] [2, 4469471, 153, 2703791] [2, 4863127, 276, 1059661] [2, 5016191, 162, 3677584] [2, 6334351, 182, 2259489] [2, 6787327, 326, 440965] [2, 7674967, 59, 3268337] [2, 8095447, 356, 2233088] [2, 8388607, 12, 4096] [2, 8727391, 18, 262144] [2, 9588151, 20, 1048576] [2, 9995671, 23, 8388608]
There seems to be no n congruent to 3 or 5 modulo 8 (a.k.a 2 is a quadratic non-residue mod n).

I replaced b=2 to b=3:

Code:
[3, 1683683, 15, 879443]
[3, 1898999, 141, 1444216]
[3, 2586083, 27, 1612472]
[3, 2795519, 171, 2214249]
[3, 4042403, 25, 940643]
[3, 4099439, 207, 3562151]
[3, 5087171, 28, 3216314]
[3, 8243111, 120, 2486937]
Similarly, there are no counterexamples that 3 is a Q non-residue mod n, or n congruent to 5 or 7 modulo 12.

Maybe there could be some undiscovered primality test associated with that?

2019-10-26, 21:12   #26
paulunderwood

Sep 2002
Database er0rr

32·7·53 Posts

Quote:
 Originally Posted by carpetpool There seems to be no n congruent to 3 or 5 modulo 8 (a.k.a 2 is a quadratic non-residue mod n). I replaced b=2 to b=3: Code: [3, 1683683, 15, 879443] [3, 1898999, 141, 1444216] [3, 2586083, 27, 1612472] [3, 2795519, 171, 2214249] [3, 4042403, 25, 940643] [3, 4099439, 207, 3562151] [3, 5087171, 28, 3216314] [3, 8243111, 120, 2486937] Similarly, there are no counterexamples that 3 is a Q non-residue mod n, or n congruent to 5 or 7 modulo 12. Maybe there could be some undiscovered primality test associated with that?
A nice observation. Base b pseudoprimes are either all such that J(b,n)==1 or are all such that J(b,n)==-1. To see the latter case feed in b=46 or b=199.

Last fiddled with by paulunderwood on 2019-10-26 at 21:39

 2019-10-28, 02:13 #27 paulunderwood     Sep 2002 Database er0rr 32×7×53 Posts b=3 For b=3 and a least odd n<10^9, pseudoprimes satisfy 2*r-1 == znorder(Mod(b,n)) (as well as carpetpool's (paul) observation that 3 is a QR) Thus without computing the order, two tests should be enough when J(3,n)==1. Alternatively make sure gcd(2*r-1,n-1)==1 Last fiddled with by paulunderwood on 2019-10-28 at 03:01
 2019-10-29, 20:50 #28 paulunderwood     Sep 2002 Database er0rr 32·7·53 Posts Algoritm for b=3 Turning the b=3 ideas into an algorithm: Code: { b_3(n)=local(a=3,r=1,k,g,BIN,LEN,va,vb); if(n==2||n==3||n==5||n==11,return(1)); if(gcd(2,n)!=1,return(0)); if(issquare(n),return(0)); if(Mod(3,n)^(n-1)!=1,return(0)); k=kronecker(a*a-4,n);g=gcd(a*a-1,n); while(k==1||g!=1||gcd(2*r-1,n-1)!=1, if(k==0||(1
2019-10-31, 01:47   #29
carpetpool

"Sam"
Nov 2016

12C16 Posts

Quote:
 Originally Posted by paulunderwood Turning the b=3 ideas into an algorithm: a will remain as 3 if n ends in 3 or 7 and so the above code could be further optimised. This a 1+2 selfridge test.
What about when n ends in 1 or 9?

2019-10-31, 02:10   #30
paulunderwood

Sep 2002
Database er0rr

32·7·53 Posts

Quote:
 Originally Posted by carpetpool What about when n ends in 1 or 9?
Then "a" gets repeatedly multiplied by "b=3" until the conditions are met.

I am not so sure about my asertion of taking gcd(2*r-1,n-1)...

I have checked the b=3 test up to 9*10^10.

I am mostly looking at b=6 which I hope to test to 1.2*10^15 for all r n a reasonable amount of time

 2019-11-27, 02:40 #31 paulunderwood     Sep 2002 Database er0rr 32×7×53 Posts Amazing any number -- a puzzle I introduce two other steps to the hitherto 2 selfridge test, being a gcd and another selfridge Let d=a^2-4 be the discriminant of x^2-a*x+1. I add the test d^((n-1)/2)==-1 (mod n). Since a=x+1/x we have a^2-2 = (x^2+1)/x^2. The original 2 selfridge test is (b*x)^((n+1)/2)=b*J(b(a+2),n) (mod n, x^2-a*x+1), But a^((n+1)/2)=b^((n+1)/2). Which is equivalent to saying the test is (x^2+1)^((n+1)/2)=b*J(b(a+2),n) (mod n, x^2-a*x+1). So, I introduce gcd(a^2-2,n)=1. Then I ran a test: Code: {for(b=1,1024,forstep(n=9,1000000,2, if(gcd(b^3-b,n)==1&&!ispseudoprime(n)&&Mod(b,n)^((n-1))==1, a=b;r=1;while(a!=1, if(kronecker(a^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a^2-2,n)==1&& Mod(a^2-4,n)^((n-1)/2)==-1&& Mod(Mod(1,n)*x*b,x^2-a*x+1)^((n+1)/2)==b*kronecker(b*(a+2),n), print([b,n,r,a]));r++;a=a*b%n))))}` No output from this two-parameter 1+2 selfridge test I shall run some tests through a script given to me by Dr. David Broadhurst to see if I can find some counterexamples. Edit: b=powers of 3 give counterexamples readily. But other b? Last fiddled with by paulunderwood on 2019-11-27 at 04:34
2019-11-27, 07:02   #32
paulunderwood

Sep 2002
Database er0rr

333910 Posts

Quote:
 Originally Posted by paulunderwood Since a=x+1/x we have a^2-2 = (x^2+1)/x^2.

That should be (x^4+1)/x^2. Amazingly the program stands for b not a power of 3.

I have tried a few b's with DB's semi-prime generator program he sent me and the results are good -- no counterexamples found.

2019-11-27, 08:45   #33
paulunderwood

Sep 2002
Database er0rr

32×7×53 Posts

Here is a short paper describing the idea
Attached Files

 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 14:37.

Sat Aug 15 14:37:47 UTC 2020 up 2 days, 11:13, 1 user, load averages: 1.07, 1.59, 1.71