mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-08-27, 17:36   #78
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,723 Posts
Lightbulb



The solutions to x^2-2*x-2^r=0 are 1 +- sqrt(1+2^r) and gives rise to the test:
  • gcd(2^r+2,n)==1
  • gcd(2^r+4,n)==1
  • kronecker(1+2^r,n)==-1
  • Mod(1+2^r,n)^((n-1)/2)==-1
  • Mod(Mod(1,n)*x,x^2-2*x-2^r)^(n+1)==-2^r

Mod(Mod(1,n)*x,x^2-2*x-2^r)^(n+1)==-2^r implies Mod(-2^r,n)^(n-1)==1. If n was prime then Mod(2,n)^(n-1)==1. This greatly increases the scope for verification, e.g. using Feitsma's PSP-2 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*(n-1)%z==0,
a=Mod(2,n)^r;if(kronecker(1+lift(a),n)==-1&&
Mod(1+a,n)^((n-1)/2)==-1&&Mod(Mod(1,n)*x,x^2-2*x-a)^(n+1)==-a,
print([n,a,gcd(a+2,n),gcd(a+4,n)]))))))}

Last fiddled with by paulunderwood on 2020-08-27 at 23:45
paulunderwood is offline   Reply With Quote
Old 2020-08-28, 03:45   #79
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

65668 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
  • gcd(2^r+2,n)==1
  • gcd(2^r+4,n)==1
  • kronecker(1+2^r,n)==-1
  • Mod(1+2^r,n)^((n-1)/2)==-1
  • Mod(Mod(1,n)*x,x^2-2*x-2^r)^(n+1)==-2^r
[n,a]=[1432999, 107552] is a counterexample.

Last fiddled with by paulunderwood on 2020-08-28 at 13:40
paulunderwood is offline   Reply With Quote
Old 2020-08-28, 13:23   #80
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,723 Posts
Default

Flipping the sign or 2^r, I am now testing:
  • gcd(2^r-2,n)==1
  • gcd(2^r-4,n)==1
  • kronecker(1-2^r,n)==-1
  • Mod(1-2^r,n)^((n-1)/2)==-1
  • Mod(Mod(1,n)*x,x^2-2*x+2^r)^(n+1)==2^r
paulunderwood is offline   Reply With Quote
Old 2020-08-28, 21:31   #81
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,723 Posts
Default

If z is the multiplicative order of 2 mod n and kronecker(1-2^r,n)==-1 then gcd(2^z-1,2^r-1)==1 which implies gcd(r,z)==1. Hence z must divide n-1. Is that right?

We know z | eulerphi(n). Lehmer's totient conjecture is unproven. But can z | n-1?

The verification code is:

Code:
{forstep(n=3,1000000000,2,
if(!ispseudoprime(n),z=znorder(Mod(2,n));
if((n-1)%z==0,for(r=1,z,if(gcd(r,z)==1,a=Mod(2,n)^r;
if(kronecker(1-lift(a),n)==-1&&(1-a)^((n-1)/2)==-1&&
Mod(x,x^2-2*x+a)^(n+1)==a,
print([n,a,gcd(a-2,n),gcd(a-4,n)])))))))}
This is very fast

Last fiddled with by paulunderwood on 2020-08-28 at 22:16
paulunderwood is offline   Reply With Quote
Old 2020-08-29, 03:49   #82
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,723 Posts
Cool

Quote:
Originally Posted by paulunderwood View Post
If z is the multiplicative order of 2 mod n and kronecker(1-2^r,n)==-1 then gcd(2^z-1,2^r-1)==1 which implies gcd(r,z)==1. Hence z must divide n-1. Is that right?

We know z | eulerphi(n). Lehmer's totient conjecture is unproven. But can z | n-1?
Since z | n-1, 2^(n-1)==1 mod n. I can use a PSP-2 list. Without ispseudoprime() the verification code moves very quickly

Last fiddled with by paulunderwood on 2020-08-29 at 03:58
paulunderwood is offline   Reply With Quote
Old 2020-08-30, 01:34   #83
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,723 Posts
Default Euler-Frobenius Probable Prime Test paper



Apologies for writing sqrt(1-2^r) in two places where it should be just 1-2^r

It should read "Euler PRP test of 1-2^r" and "Jacobi symbol of 1-2^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,
Attached Files
File Type: pdf Euler-Frobenius_Probable_Prime_Test.pdf (41.7 KB, 49 views)

Last fiddled with by paulunderwood on 2020-09-23 at 22:52
paulunderwood is offline   Reply With Quote
Old 2020-09-03, 23:33   #84
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,723 Posts
Default

This latest test is looking good. I have run David Broadhurst's semiprime-CRT 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
Attached Files
File Type: txt Euler-Frobenius.log.txt (3.2 KB, 5 views)

Last fiddled with by paulunderwood on 2020-10-02 at 11:10
paulunderwood is offline   Reply With Quote
Old 2020-09-10, 05:04   #85
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101011101102 Posts
Arrow 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 Euler-Frobenius.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.
Attached Files
File Type: c Euler-Frobenius.cpp.c (5.2 KB, 14 views)

Last fiddled with by paulunderwood on 2020-09-13 at 10:40
paulunderwood is offline   Reply With Quote
Old 2020-09-15, 10:44   #86
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,723 Posts
Default test based on FLT proof n=4

In the previous I had x=1+-sqrt(1-2^r). I note that 2^r-1 (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 non-square n:
  • gcd(a,n)==1
  • gcd(b^4-1,n)==1
  • gcd(2*a^4+b^4,n)==1
  • gcd(4*a^4+b^4,n)==1
  • kronecker(a^4+b^4,n)==-1
  • Mod(a^4+b^4,n)^((n-1)/2)==-1
  • Mod(Mod(1,n)*x,x^2-2*a^2*x-b^4)^(n+1)==-b^4



The quadratic has solutions x=a^2+-sqrt(a^4+b^4) and so maybe I should be doing a base-a Fermat PRP test too. Anyway letting a=1 simplifies things greatly.

Last fiddled with by paulunderwood on 2020-09-15 at 13:25 Reason: dropped gcd(b^4+a^2,n)==1 after testing
paulunderwood is offline   Reply With Quote
Old 2020-09-15, 14:06   #87
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

344610 Posts
Default

I made a mistake: Case 4 of FLT uses the fact a^4-b^4 is never a square. So I have to flip the sign to get:
  • gcd(a,n)==1
  • gcd(b^4-1,n)==1
  • gcd(2*a^4-b^4,n)==1
  • gcd(4*a^4-b^4,n)==1
  • kronecker(a^4-b^4,n)==-1
  • Mod(a^4-b^4,n)^((n-1)/2)==-1
  • Mod(Mod(1,n)*x,x^2-2*a^2*x+b^4)^(n+1)==b^4

Letting a=1 simplifies the quadratic equation solution to x=1+-sqrt(1-b^4)

For a=1. the n that require GCDs are the same as those for the tests on x=1+-(1-2^r) except have more examples (for each n).

Last fiddled with by paulunderwood on 2020-09-15 at 15:17
paulunderwood is offline   Reply With Quote
Old 2020-09-15, 18:52   #88
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,723 Posts
Default Efficiencies

Using Euler+Frobenius on x=1+-sqrt(1-b^4). For intermediate values s*x+t in left-right exponentiation of the Frobenius test we have:-

Squaring:
Code:
? Mod(s*x+t,x^2-2*x+b^4)^2
Mod((2*s^2 + 2*t*s)*x + (-b^4*s^2 + t^2), x^2 - 2*x + b^4)
Multiplying by the base x if the bit is 1:
Code:
? Mod(s*x+t,x^2-2*x+b^4)*x
Mod((2*s + t)*x - b^4*s, x^2 - 2*x + b^4)
Hence for small b squaring is 2 selfridges because all we need to calculate is 2*s*(s+t) and (t-b^2*s)*(t+b^2*s)



Edit: Counterexample to x=1+-sqrt(1-b^4):

Code:
? [n,b]=[2579*30937, 16641097];kronecker(1-b^4,n)==-1&&gcd(2-b^4,n)==1&&gcd(4-b^4,n)==1&&Mod(1-b^4,n)^((n-1)/2)==-1&&Mod(Mod(1,n)*x,x^2-2*x+b^4)^(n+1)==b^4
1

Last fiddled with by paulunderwood on 2020-09-15 at 19:48
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 22:29.

Wed Oct 28 22:29:46 UTC 2020 up 48 days, 19:40, 1 user, load averages: 3.16, 3.20, 2.87

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.