20200827, 17:36  #78 
Sep 2002
Database er0rr
D76_{16} Posts 
The solutions to x^22*x2^r=0 are 1 + sqrt(1+2^r) and gives rise to the test:
Mod(Mod(1,n)*x,x^22*x2^r)^(n+1)==2^r implies Mod(2^r,n)^(n1)==1. If n was prime then Mod(2,n)^(n1)==1. This greatly increases the scope for verification, e.g. using Feitsma's PSP2 database. Edit: This verification code uses this idea: Code:
{forstep(n=3,1000000,2,if(!ispseudoprime(n), z=znorder(Mod(2,n));for(r=1,z,if(r*(n1)%z==0, a=Mod(2,n)^r;if(kronecker(1+lift(a),n)==1&& Mod(1+a,n)^((n1)/2)==1&&Mod(Mod(1,n)*x,x^22*xa)^(n+1)==a, print([n,a,gcd(a+2,n),gcd(a+4,n)]))))))} Last fiddled with by paulunderwood on 20200827 at 23:45 
20200828, 03:45  #79 
Sep 2002
Database er0rr
3446_{10} Posts 
[n,a]=[1432999, 107552] is a counterexample.
Last fiddled with by paulunderwood on 20200828 at 13:40 
20200828, 13:23  #80 
Sep 2002
Database er0rr
2·1,723 Posts 
Flipping the sign or 2^r, I am now testing:

20200828, 21:31  #81 
Sep 2002
Database er0rr
2·1,723 Posts 
If z is the multiplicative order of 2 mod n and kronecker(12^r,n)==1 then gcd(2^z1,2^r1)==1 which implies gcd(r,z)==1. Hence z must divide n1. Is that right?
We know z  eulerphi(n). Lehmer's totient conjecture is unproven. But can z  n1? The verification code is: Code:
{forstep(n=3,1000000000,2, if(!ispseudoprime(n),z=znorder(Mod(2,n)); if((n1)%z==0,for(r=1,z,if(gcd(r,z)==1,a=Mod(2,n)^r; if(kronecker(1lift(a),n)==1&&(1a)^((n1)/2)==1&& Mod(x,x^22*x+a)^(n+1)==a, print([n,a,gcd(a2,n),gcd(a4,n)])))))))} Last fiddled with by paulunderwood on 20200828 at 22:16 
20200829, 03:49  #82  
Sep 2002
Database er0rr
2·1,723 Posts 
Quote:
Last fiddled with by paulunderwood on 20200829 at 03:58 

20200830, 01:34  #83 
Sep 2002
Database er0rr
2·1,723 Posts 
EulerFrobenius Probable Prime Test paper
Apologies for writing sqrt(12^r) in two places where it should be just 12^r It should read "Euler PRP test of 12^r" and "Jacobi symbol of 12^r over n" Fixed. There is a logical flaw in this paper. I cannot assume gcd(r,z)=1. The verification has reached only 4*10^6. You can find a "flawless" replacement paper here, Last fiddled with by paulunderwood on 20200923 at 22:52 
20200903, 23:33  #84 
Sep 2002
Database er0rr
2·1,723 Posts 
This latest test is looking good. I have run David Broadhurst's semiprimeCRT algorithm without finding a counterexample. I have also written a C+primesieve+Pari program  I needed a good solution to znorder  and it is very fast. What took nearly a week in pure Pari/GP (8.75E6) will take a few hours with this program. I will post an edit in this post to show how far the program has verified.
Final update: no pseudoprimes < 10^8 Last fiddled with by paulunderwood on 20201002 at 11:10 
20200910, 05:04  #85 
Sep 2002
Database er0rr
6566_{8} Posts 
C++ code
I have attached the C/C++ code I am using to verify the above test.
I would appreciate any ideas for improvements that can be done. One idea is to have a threshold based on the size of z. If the order is small then it might be quicker to have functions based on "%" rather than my quick three_section_mod. Note that the program needs the file EulerFrobenius.dat containing something like 11 1000000000 BTW, I use primesive 4.4 Edit: I changed the code so there is one call to primesieve. Also masks are precomputed. I also introduced "threshold". The resulting code is 20% faster. Edit2. Dropped unsigned int. Using global variables. More clean up and cosmetics. Edit3. Polished version. Remove ".c" extension to get the C++ file. Last fiddled with by paulunderwood on 20200913 at 10:40 
20200915, 10:44  #86 
Sep 2002
Database er0rr
D76_{16} Posts 
test based on FLT proof n=4
In the previous I had x=1+sqrt(12^r). I note that 2^r1 (r>1) is never a square. So what else is never a square? In his proof of FLT case n=4 Fermat showed a^4+b^4 is never a square, which leads me onto the following test for odd nonsquare n:
The quadratic has solutions x=a^2+sqrt(a^4+b^4) and so maybe I should be doing a basea Fermat PRP test too. Anyway letting a=1 simplifies things greatly. Last fiddled with by paulunderwood on 20200915 at 13:25 Reason: dropped gcd(b^4+a^2,n)==1 after testing 
20200915, 14:06  #87 
Sep 2002
Database er0rr
2·1,723 Posts 
I made a mistake: Case 4 of FLT uses the fact a^4b^4 is never a square. So I have to flip the sign to get:
Letting a=1 simplifies the quadratic equation solution to x=1+sqrt(1b^4) For a=1. the n that require GCDs are the same as those for the tests on x=1+(12^r) except have more examples (for each n). Last fiddled with by paulunderwood on 20200915 at 15:17 
20200915, 18:52  #88 
Sep 2002
Database er0rr
2·1,723 Posts 
Efficiencies
Using Euler+Frobenius on x=1+sqrt(1b^4). For intermediate values s*x+t in leftright exponentiation of the Frobenius test we have:
Squaring: Code:
? Mod(s*x+t,x^22*x+b^4)^2 Mod((2*s^2 + 2*t*s)*x + (b^4*s^2 + t^2), x^2  2*x + b^4) Code:
? Mod(s*x+t,x^22*x+b^4)*x Mod((2*s + t)*x  b^4*s, x^2  2*x + b^4) Edit: Counterexample to x=1+sqrt(1b^4): Code:
? [n,b]=[2579*30937, 16641097];kronecker(1b^4,n)==1&&gcd(2b^4,n)==1&&gcd(4b^4,n)==1&&Mod(1b^4,n)^((n1)/2)==1&&Mod(Mod(1,n)*x,x^22*x+b^4)^(n+1)==b^4 1 Last fiddled with by paulunderwood on 20200915 at 19:48 
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 