20191129, 00:39  #34 
Sep 2002
Database er0rr
3^{2}·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^2a*x+1=0:
\[x=\frac{a\pm \sqrt{\Delta}}{2}\] where \[\Delta = a^24\] This can be rewritten as: \[2x = a \pm \sqrt{\Delta}\] Now I propose a test where a=b^r for any appropriate r:
The last 3 conditions are almost like a Fematian triple (aka FLT). Then (2*x)^n = 2/x (mod n, x^2a*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 20191130 at 01:30 Reason: correctiion to solution of x 
20191129, 23:05  #35  
Sep 2002
Database er0rr
6413_{8} Posts 
Quote:
Here is the variation of David Broadhurst's script I am using to test various semiprimes for different b: Code:
{tst(n,x,b)=gcd(x^3x,n)==1&&kronecker(x^24,n)==1&&gcd(x^22,n)==1&& Mod(b,n)^(n1)==1&&Mod(x^24,n)^((n1)/2)==1&& Mod(Mod(1,n)*2*L,L^2x*L+1)^((n+1)/2)==2*kronecker(2*(x+2),n);} {tst1(p,q,b)=local(n=p*q,u=[]); for(a=3,p3,if((n%(p1)==1(Mod(b,p)^(n1)==1))&& Mod(Mod(1,p)*2*L,L^2a*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*(p1); if(ispseudoprime(q)&&Mod(2,p*q)^(p*q)==2&&Mod(b,p*q)^(p*q1)==1,tst2(p,q,b)))); print("\\\\ "round(gettime/1000)" seconds");} Last fiddled with by paulunderwood on 20191129 at 23:32 

20191130, 20:21  #36  
Sep 2002
Database er0rr
D0B_{16} Posts 
Quote:
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 20191201 at 01:28 

20191202, 10:53  #37 
Sep 2002
Database er0rr
3^{2}·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^2a*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 20191202 at 11:10 
20191202, 12:03  #38 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
2^{6}·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://millerrabin.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 MillerRabin 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)? 
20191203, 03:28  #39  
Sep 2002
Database er0rr
3^{2}×7×53 Posts 
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
Last fiddled with by paulunderwood on 20191203 at 03:59 

20191206, 09:16  #40 
Sep 2002
Database er0rr
3^{2}×7×53 Posts 
Work in progress
The attached paper is the final draft!
Last fiddled with by paulunderwood on 20191231 at 16:35 
20191216, 09:59  #41 
Sep 2002
Database er0rr
3^{2}·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 semiprimes.

20191222, 08:02  #42 
Sep 2002
Database er0rr
3^{2}·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:
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 20191222 at 10:56 
20191222, 14:34  #43  
Feb 2017
Nowhere
2^{2}×839 Posts 
Quote:
My ancient PariGP manual says (my emphasis) Quote:
Quote:


20191222, 17:14  #44 
Sep 2002
Database er0rr
3^{2}·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 20191222 at 17:42 
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  20180201 05:40 
Amazing result in P1  Miszka  Information & Answers  2  20140704 17:11 
Amazing academic resource  Xyzzy  Lounge  6  20120325 22:57 
Amazing!!!  R.D. Silverman  Factoring  5  20060126 09:14 
Two Amazing Things  clowns789  Hardware  1  20031227 16:57 