mersenneforum.org Amazing 6
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2019-11-29, 00:39 #34 paulunderwood     Sep 2002 Database er0rr 32·7·53 Posts Another Quadratic Frobenius Test with Two Free Parameters Sure you know how to solve x for a quadratic equation, in particular x^2-a*x+1=0: $x=\frac{a\pm \sqrt{\Delta}}{2}$ where $\Delta = a^2-4$ This can be rewritten as: $2x = a \pm \sqrt{\Delta}$ Now I propose a test where a=b^r for any appropriate r: n is odd and non-square b is not a power of 3 deal with trivial n gcd(b^3-b,n) == 1 gcd(a^2-1,n) == 1 gcd(a^2-2,n) == 1 kronecker(a^2-4,n) == -1 Mod(a^2-4,n)^((n-1)/2) == -1 Mod(b,n)^(n-1) == 1 Mod(Mod(1,n)*2*x,x^2-a*x+1)^((n+1)/2) == 2*kronecker(2*(a+2),n) The last 3 conditions are almost like a Fematian triple (aka FLT). Then (2*x)^n = 2/x (mod n, x^2-a*x+1); a^n = a (mod n); and sqrt(delta)^n = -sqrt(delta) (mod n) -- but does this help? Last fiddled with by paulunderwood on 2019-11-30 at 01:30 Reason: correctiion to solution of x
2019-11-29, 23:05   #35
paulunderwood

Sep 2002
Database er0rr

64138 Posts

Quote:
 Originally Posted by paulunderwood n is odd and non-square b is not a power of 3 deal with trivial n gcd(b^3-b,n) == 1 gcd(a^2-1,n) == 1 gcd(a^2-2,n) == 1 kronecker(a^2-4,n) == -1 Mod(a^2-4,n)^((n-1)/2) == -1 Mod(b,n)^(n-1) == 1 Mod(Mod(1,n)*2*x,x^2-a*x+1)^((n+1)/2) == 2*kronecker(2*(a+2),n)
Step 10 implies n is 2-PRP,

Here is the variation of David Broadhurst's script I am using to test various semi-primes for different b:

Code:
{tst(n,x,b)=gcd(x^3-x,n)==1&&kronecker(x^2-4,n)==-1&&gcd(x^2-2,n)==1&&
Mod(b,n)^(n-1)==1&&Mod(x^2-4,n)^((n-1)/2)==-1&&
Mod(Mod(1,n)*2*L,L^2-x*L+1)^((n+1)/2)==2*kronecker(2*(x+2),n);}

{tst1(p,q,b)=local(n=p*q,u=[]);
for(a=3,p-3,if((n%(p-1)==1||(Mod(b,p)^(n-1)==1))&&
Mod(Mod(1,p)*2*L,L^2-a*L+1)^(n+1)==4,
u=concat(u,a)));Mod(u,p);}

{tst2(p,q,b)=local(n=p*q,up,uq,a,V=[]);
up=tst1(p,q,b);if(#up,uq=tst1(q,p,b);if(#uq,
for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
if(tst(n,a,b),V=concat(V,a))))));V=vecsort(V);
if(#V,for(k=1,#V,print([n,V[k],znlog(V[k],Mod(b,n))])));V;}

{b=3;forprime(p=7,40000000,for(k=4,6,q=1+2*k*(p-1);
if(ispseudoprime(q)&&Mod(2,p*q)^(p*q)==2&&Mod(b,p*q)^(p*q-1)==1,tst2(p,q,b))));
print("\\\\ "round(gettime/1000)" seconds");}
An empty vector at the end of a line means a is not in b's orbit, For b=3 (and of powers of 3) there might be a number --- for b=3 this is exactly half the multiplicative order plus 1 of 3.

Last fiddled with by paulunderwood on 2019-11-29 at 23:32

2019-11-30, 20:21   #36
paulunderwood

Sep 2002
Database er0rr

D0B16 Posts

Quote:
 Originally Posted by paulunderwood n is odd and non-square b is not a power of 3 deal with trivial n gcd(b^3-b,n) == 1 gcd(a^2-1,n) == 1 gcd(a^2-2,n) == 1 kronecker(a^2-4,n) == -1 Mod(a^2-4,n)^((n-1)/2) == -1 Mod(b,n)^(n-1) == 1 Mod(Mod(1,n)*2*x,x^2-a*x+1)^((n+1)/2) == 2*kronecker(2*(a+2),n)
Choosing b=2 reduces the number of selfridges from 1+1+2 to 1+2 when examining x^2-2^r*x+1=0 or 2*x=2^r +/- sqrt(2^(2*r)-4):
1. n is non-square
2. gcd(6,n) == 1
3. gcd(a^2-1,n) == 1
4. gcd(a^2-2,n) == 1
5. kronecker(a^2-4,n) == -1
6. Mod(a^2-4,n)^((n-1)/2) == -1
7. Mod(Mod(1,n)*2*x,x^2-a*x+1)^((n+1)/2) == 2*kronecker(2*(a+2),n)

I have tested the first 6517 odd Carmichael numbers (C_n<=520,178,982,961) with all appropriate r.

Last fiddled with by paulunderwood on 2019-12-01 at 01:28

 2019-12-02, 10:53 #37 paulunderwood     Sep 2002 Database er0rr 32·7·53 Posts I have now reached the Carmichael number 6,969,354,856,321 for the previous test, I am thinking of writing a paper detailing on why the gcds are chosen, on how to square roots over x^2-a*x+1, on the various variations in this thread under "Another Quadratic Frobenius Test with Two Free Parameters", and publishing it. Do you think it will be worth doing? Last fiddled with by paulunderwood on 2019-12-02 at 11:10
 2019-12-02, 12:03 #38 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT) 26·89 Posts I think there are a few things that would make it publishable IMO: 1. It is a provable primality test. This seems very hard to prove if it is even true. 2. It is a probable primality test faster than existing methods. It would also need a good lower bound on counterexamples(at least 2^64). Can it beat 7 SPRP tests for speed up to 2^64? https://miller-rabin.appspot.com/ 3. It is a novel method that comes close to 2 and has the potential for improvement either towards 1 or 2. I am not sure how much it being novel would stretch(or if it indeed is). 4. It can add certainty to other tests such as BPSW. It would need showing that some hypothetical BPSW counterexamples would stand a chance of failing this test. i.e. that the BPSW test doesn't imply this result. BPSW is an example here. Insert the test of choice. 5. An upper bound on the probability of failing multiple tests similar to the Miller-Rabin test. Would probably need to beat 4^-k or come close. RDS would be a good person to comment on this although I suspect I know his answer. Does anyone have any additions to my list(or arguments against any items)?
2019-12-03, 03:28   #39
paulunderwood

Sep 2002
Database er0rr

32×7×53 Posts

Quote:
 Originally Posted by henryzz I think there are a few things that would make it publishable IMO: 1. It is a provable primality test. This seems very hard to prove if it is even true.
I am very much thinking about this. Trying to prove it will be hard. Top mathematicians could look into it.
Quote:
 2. It is a probable primality test faster than existing methods. It would also need a good lower bound on counterexamples(at least 2^64). Can it beat 7 SPRP tests for speed up to 2^64? https://miller-rabin.appspot.com/
The 1+2 selfridge b=2 variant works for n<2^64 and r minimal. without using the sqrt(Delta) component i.e. 2 selfridges only.
Quote:
 3. It is a novel method that comes close to 2 and has the potential for improvement either towards 1 or 2. I am not sure how much it being novel would stretch(or if it indeed is).
It is a novel ansatz, being based on a simple solution to x^2-b^r*x+1=0
Quote:
 4. It can add certainty to other tests such as BPSW. It would need showing that some hypothetical BPSW counterexamples would stand a chance of failing this test. i.e. that the BPSW test doesn't imply this result. BPSW is an example here. Insert the test of choice.
I'd say it is better than BPSW in that BPSW does not have any parameters and for some non-minimal values BPSW fails. My test uses 2 parameters!
Quote:
 5. An upper bound on the probability of failing multiple tests similar to the Miller-Rabin test. Would probably need to beat 4^-k or come close.
I don't know how to do the analysis, but all testing done by me fails to find a single counterexample
Quote:
 RDS would be a good person to comment on this although I suspect I know his answer.
Maybe if I write the paper someone respectable might referee it.
Quote:
 Does anyone have any additions to my list(or arguments against any items)?

Last fiddled with by paulunderwood on 2019-12-03 at 03:59

2019-12-06, 09:16   #40
paulunderwood

Sep 2002
Database er0rr

32×7×53 Posts
Work in progress

The attached paper is the final draft!
Attached Files
 A_Quadratic_Frobenius_Composite_Test_with_Two_Free_Parameters.pdf (57.7 KB, 33 views)

Last fiddled with by paulunderwood on 2019-12-31 at 16:35

 2019-12-16, 09:59 #41 paulunderwood     Sep 2002 Database er0rr 32·7·53 Posts The paper in the previous post is complete AFAIC. Reading it you will that Carmichael numbers < 10^14 have been tested along with certain semi-primes.
 2019-12-22, 08:02 #42 paulunderwood     Sep 2002 Database er0rr 32·7·53 Posts In the above paper I stated that it is sufficient to test with minimal r for n<2^64 where a=2^r: gcd(6,n)==1 gcd(a^2-1,n)==1 gcd(a^2-2,n)==1 !issquare(n) kronecker(a^2-4,n)==-1 Mod(Mod1,n)*2*x,x^2-a*x+1)^((n+1)/2)==2*kronecker(2*(a+2),n) Puzzle: use any r rather than a minimal r to find a counterexample. I have tested n< 10^10 and counting. Last fiddled with by paulunderwood on 2019-12-22 at 10:56
2019-12-22, 14:34   #43
Dr Sardonicus

Feb 2017
Nowhere

22×839 Posts

Quote:
 Originally Posted by paulunderwood In the above paper I stated that it is sufficient to test with minimal r for n<2^64 where a=2^r: gcd(6,n)==1 gcd(a^2-1,n)==1 gcd(a^2-2,n)==1 !issquare(n) kronecker(a^2-4,n)==-1 Mod(Mod1,n)*2*x,x^2-a*x+1)^((n+1)/2)==2*kronecker(2*(a+2),n) Puzzle: use any r rather than a minimal r to find a counterexample. I have tested n< 10^10 and counting.
Judging by what is known or suspected about BPSW, in looking for exceptions you might have your work cut out for you.

My ancient Pari-GP manual says (my emphasis)
Quote:
 There are no known composite numbers passing this test (in particular, all composites $\le$ 1013 are correctly detected), although it is expected that inﬁnitely many such numbers exist.
According to the Wolfram Mathworld page on the Baillie-PSW Primality Test,
Quote:
 No examples of composite numbers passing the test are known, and as of June 13, 2009, Jeff Gilchrist has confirmed that there are no Baillie-PSW pseudoprimes up to 1017. However, the elliptic curve primality proving program PRIMO checks all intermediate probable primes with this test, and if any were composite, the certification would necessarily have failed. Based on the fact that this has not occurred in three years of usage, PRIMO author M. Martin estimates that there is no composite less than about 10000 digits that can fool this test.

 2019-12-22, 17:14 #44 paulunderwood     Sep 2002 Database er0rr 32·7·53 Posts Thanks, Dr Sardonicus, for the perspective on BPSW. I have reached 10^11 (using GMP rather than Pari/GP) and the test holds for all r for the 2 selfridge variant. That is #psp2 coprime to 6 times the average multiplicative order of 2 tests without finding a counterexample. I will continue to 10^12 before adding a note in my paper and maybe much higher at a later date, although 10^15 seems to be about the limit given my resources and time. There is no chance of testing all r for PSP2 under 2^64 let alone 10^10000 Last fiddled with by paulunderwood on 2019-12-22 at 17:42

 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:59.

Sat Aug 15 14:59:03 UTC 2020 up 2 days, 11:34, 1 user, load averages: 1.97, 1.90, 1.80