mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-10-26, 02:21   #23
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

1001011002 Posts
Post

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?
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?
carpetpool is offline   Reply With Quote
Old 2019-10-26, 02:31   #24
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-10-26, 20:36   #25
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×3×52 Posts
Post

Quote:
Originally Posted by paulunderwood View Post
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?
carpetpool is offline   Reply With Quote
Old 2019-10-26, 21:12   #26
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-10-28, 02:13   #27
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default 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
paulunderwood is offline   Reply With Quote
Old 2019-10-29, 20:50   #28
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default 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<g&&g<n),return(0),a=(a*3)%n;k=kronecker(a*a-4,n);g=gcd(a*a-1,n);r++));
va=2;vb=a;BIN=binary(n);LEN=length(BIN)-1;
for(k=1,LEN,
  if(BIN[k],va=(va*vb-a)%n;vb=(vb*vb-2)%n,vb=(va*vb-a)%n;va=(va*va-2)%n));
k=kronecker(a+2,n);return(va==(a*k)%n&&vb==(2*k)%n)
}
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.

Last fiddled with by paulunderwood on 2019-10-29 at 21:13
paulunderwood is offline   Reply With Quote
Old 2019-10-31, 01:47   #29
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

12C16 Posts
Post

Quote:
Originally Posted by paulunderwood View Post
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?
carpetpool is offline   Reply With Quote
Old 2019-10-31, 02:10   #30
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

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

32×7×53 Posts
Default 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
paulunderwood is offline   Reply With Quote
Old 2019-11-27, 07:02   #32
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

333910 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
paulunderwood is offline   Reply With Quote
Old 2019-11-27, 08:45   #33
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default

Here is a short paper describing the idea
Attached Files
File Type: pdf A_Quadratic_Frobenius_Test_with_Two_Free_Parameters.pdf (39.1 KB, 49 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 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

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.