mersenneforum.org Amazing 6
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-27, 17:36 #78 paulunderwood     Sep 2002 Database er0rr 2·1,723 Posts 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
2020-08-28, 03:45   #79
paulunderwood

Sep 2002
Database er0rr

65668 Posts

Quote:
 Originally Posted by paulunderwood 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

 2020-08-28, 13:23 #80 paulunderwood     Sep 2002 Database er0rr 2×1,723 Posts 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
 2020-08-28, 21:31 #81 paulunderwood     Sep 2002 Database er0rr 2·1,723 Posts 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
2020-08-29, 03:49   #82
paulunderwood

Sep 2002
Database er0rr

2×1,723 Posts

Quote:
 Originally Posted by paulunderwood 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

2020-08-30, 01:34   #83
paulunderwood

Sep 2002
Database er0rr

2·1,723 Posts
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
 Euler-Frobenius_Probable_Prime_Test.pdf (41.7 KB, 49 views)

Last fiddled with by paulunderwood on 2020-09-23 at 22:52

2020-09-03, 23:33   #84
paulunderwood

Sep 2002
Database er0rr

2×1,723 Posts

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
 Euler-Frobenius.log.txt (3.2 KB, 5 views)

Last fiddled with by paulunderwood on 2020-10-02 at 11:10

2020-09-10, 05:04   #85
paulunderwood

Sep 2002
Database er0rr

1101011101102 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 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
 Euler-Frobenius.cpp.c (5.2 KB, 14 views)

Last fiddled with by paulunderwood on 2020-09-13 at 10:40

 2020-09-15, 10:44 #86 paulunderwood     Sep 2002 Database er0rr 2·1,723 Posts 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
 2020-09-15, 14:06 #87 paulunderwood     Sep 2002 Database er0rr 344610 Posts 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
 2020-09-15, 18:52 #88 paulunderwood     Sep 2002 Database er0rr 2·1,723 Posts 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

 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 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