mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-11-29, 00:39   #34
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default 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:
  1. n is odd and non-square
  2. b is not a power of 3
  3. deal with trivial n
  4. gcd(b^3-b,n) == 1
  5. gcd(a^2-1,n) == 1
  6. gcd(a^2-2,n) == 1
  7. kronecker(a^2-4,n) == -1
  8. Mod(a^2-4,n)^((n-1)/2) == -1
  9. Mod(b,n)^(n-1) == 1
  10. 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
paulunderwood is offline   Reply With Quote
Old 2019-11-29, 23:05   #35
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

64138 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
  1. n is odd and non-square
  2. b is not a power of 3
  3. deal with trivial n
  4. gcd(b^3-b,n) == 1
  5. gcd(a^2-1,n) == 1
  6. gcd(a^2-2,n) == 1
  7. kronecker(a^2-4,n) == -1
  8. Mod(a^2-4,n)^((n-1)/2) == -1
  9. Mod(b,n)^(n-1) == 1
  10. 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
paulunderwood is offline   Reply With Quote
Old 2019-11-30, 20:21   #36
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D0B16 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
  1. n is odd and non-square
  2. b is not a power of 3
  3. deal with trivial n
  4. gcd(b^3-b,n) == 1
  5. gcd(a^2-1,n) == 1
  6. gcd(a^2-2,n) == 1
  7. kronecker(a^2-4,n) == -1
  8. Mod(a^2-4,n)^((n-1)/2) == -1
  9. Mod(b,n)^(n-1) == 1
  10. 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
paulunderwood is offline   Reply With Quote
Old 2019-12-02, 10:53   #37
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2019-12-02, 12:03   #38
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

26·89 Posts
Default

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)?
henryzz is online now   Reply With Quote
Old 2019-12-03, 03:28   #39
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-12-06, 09:16   #40
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default Work in progress

The attached paper is the final draft!

Last fiddled with by paulunderwood on 2019-12-31 at 16:35
paulunderwood is offline   Reply With Quote
Old 2019-12-16, 09:59   #41
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

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.

paulunderwood is offline   Reply With Quote
Old 2019-12-22, 08:02   #42
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2019-12-22, 14:34   #43
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×839 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2019-12-22, 17:14   #44
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

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

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

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.