mersenneforum.org 3 mod 4 with free parameter
 Register FAQ Search Today's Posts Mark Forums Read

 2022-07-17, 16:29 #1 paulunderwood     Sep 2002 Database er0rr 2·3·52·29 Posts 3 mod 4 with free parameter Consider [a,-1;1,a] = 2*a + [-a,-1;1,-a] where M=[a,-1;1,a] has the character x^2-2*a*x+a^2+1 and its discriminant = -1. Solving the character gives x=a+-sqrt(-1), leading to a test: Code: {tst(n,a)=n%4==3&& gcd(a^3-a,n)==1&& Mod(2,n)^(n-1)==1&& Mod(a,n)^(n-1)==1&& Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;} Received wisdom says this test should have counterexamples. Puzzle: can you find one? Last fiddled with by paulunderwood on 2022-07-17 at 17:38
 2022-07-17, 20:34 #2 paulunderwood     Sep 2002 Database er0rr 435010 Posts Answer: [n, a]=[79786523, 1056446] Now for a harder problem: Let a = 2^r, so that the test becomes: Code: {tst(n,r)=local(a=lift(Mod(2,n)^r)); n%4==3&& gcd(a^3-a,n)==1&& Mod(2,n)^(n-1)==1&& Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;} Last fiddled with by paulunderwood on 2022-07-17 at 20:50
2022-07-18, 18:26   #3
paulunderwood

Sep 2002
Database er0rr

435010 Posts

Quote:
 Originally Posted by paulunderwood Now for a harder problem: Let a = 2^r, so that the test becomes: Code: {tst(n,r)=local(a=lift(Mod(2,n)^r)); n%4==3&& gcd(a^3-a,n)==1&& Mod(2,n)^(n-1)==1&& Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;}
Finding a counterexample to this looks hopeless. Before my computer crashed under the heat of the day, it had reached 4e11. I suspect a counterexample at maybe 25 digits or more. Very much more for r=1

2022-07-18, 23:48   #4
paulunderwood

Sep 2002
Database er0rr

2·3·52·29 Posts

Quote:
 Originally Posted by paulunderwood Code: {tst(n,r)=local(a=lift(Mod(2,n)^r)); n%4==3&& gcd(a^3-a,n)==1&& Mod(2,n)^(n-1)==1&& Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;}
Rather than computing gcd(a^3-a,n)==1 I think gcd(r,(n-1)/2)==1 is better. Certainly verification testing is quicker (both over znorder).

Note n divides 2^(n-1)-1.

gcd(a^2-1,n)==1 ==> gcd(2^(2*r)-1,2^(n-1)-1)==1 ==> gcd(2*r,n-1)==2 if gcd(r,(n-1)/2)==1.

Hence the required condition gcd(2,n-1)==2 which is met for n==3 mod 4.

Last fiddled with by paulunderwood on 2022-07-19 at 02:53

 2022-07-19, 18:03 #5 paulunderwood     Sep 2002 Database er0rr 435010 Posts Let z=znorder(Mod(2,n)). Then [2^(z-r),-1;1,2^(z-r)]^(n+1) == 4^(z-r)+1 == (4^z+4^r)/(4^r) == (1+4^r)/4^r all mod n So 2^(r*(n+1))*[2^-r,-1;1,2^-r]^(n+1) = (1+4^r)*2^(r*(n-1)) mod n Or [1,-2^r;2^r,1]^(n+1) == 4^r +1 == [2^r,-1;1,2^r]^(n+1) mod n Hence I need only verify 0
 2022-08-18, 15:26 #6 paulunderwood     Sep 2002 Database er0rr 2·3·52·29 Posts Recap: I am testing: Fermat 2-prp and (x+2^r)^(n+1)==4^r+1 where gcd(r,n-1)==1, and have reached n<4*10^14 without counterexample. Now, writing a=lift(Mod(2,n)^r) the Lucas part can be written as a Lucas test for y over y^2-2*a*y+a^2+1 which can be transformed into Euler-PRP for a^2+1 and z^((n+1)/2)==kronecker(a^2+1,n) (mod n, z^2-2*(a^2-1)/(a^2+1)*z+1). In testing this I have found that a 2-PRP plus the Lucas test on z with gcd(a^2+1,n)==1 (and gcd(r,n-1)==1) is enough without the Euler test Last fiddled with by paulunderwood on 2022-08-18 at 15:28
 2022-08-19, 04:47 #7 paulunderwood     Sep 2002 Database er0rr 10FE16 Posts A small observation: If a number n==3 mod 4 is Fermat 2-PRP then 2^(n-1)==1 mod n. If z is the multiplicative order of 2 mod n, then z divides n-1. Also (x+2^z) == x+1 mod n. Furthermore, (x+1)^(n+1) == 2 (mod n, x^2+1) is equivalent to a Fermat 2-PRP test. Neat, eh? And gcd(r,n-1) implies gcd(r,z)==1.
2022-08-19, 14:18   #8
paulunderwood

Sep 2002
Database er0rr

10FE16 Posts

Quote:
 Originally Posted by paulunderwood A small observation: If a number n==3 mod 4 is Fermat 2-PRP then 2^(n-1)==1 mod n. If z is the multiplicative order of 2 mod n, then z divides n-1. Also (x+2^z) == x+1 mod n. Furthermore, (x+1)^(n+1) == 2 (mod n, x^2+1) is equivalent to a Fermat 2-PRP test. Neat, eh? And gcd(r,n-1) implies gcd(r,z)==1.
On this theme, since n==3 mod 4 then n-1 is divisible by 2 and not 4. Then the only possible strengthening is a base 2 Euler PRP. That is up to multiplicative order, there seems to be one or two possible solutions for gcd(r,z)>1 to (x+2^r)^(n+1) == 4^r+1 (mod n, x^2+1).

Does anyone care to complete the proof of the test?

 2022-08-19, 19:23 #9 paulunderwood     Sep 2002 Database er0rr 10FE16 Posts Summarizing the two cases: n%8=3 :: 2^((n-1)/2) == -1 mod n :: z/2 is odd :: two solutions exist: z and z/2 n%8=7 :: 2^((n-1)/2 == 1 mod n :: z is odd :: one solution exists. Due to z being on average much smaller than n, what appears to be true might be the law of small numbers.The leap from Fermat 2-PRP plus (x+2^r)^(n+1) == 4^r+1 (mod n, x^2+1) with gcd(r,n-1) == 1 to only a test for (x+2)^(n+1) == 5 (mod n,x^2+1) is a large one. Is it better to push the testing boundary beyond my 2^50 limit for the latter or to try and prove Euler 2-PRP + the test for (x+2)? Last fiddled with by paulunderwood on 2022-08-20 at 17:47 Reason: noting z/2 is odd
2022-08-20, 19:47   #10
paulunderwood

Sep 2002
Database er0rr

2·3·52·29 Posts

Quote:
 Originally Posted by paulunderwood Summarizing the two cases: n%8=3 :: 2^((n-1)/2) == -1 mod n :: z/2 is odd :: two solutions exist: z and z/2 n%8=7 :: 2^((n-1)/2 == 1 mod n :: z is odd :: one solution exists.
I forgot to add in an counting increment in my testing code. There are other cases.

I'll call it day after verification to 10^15 of the test:

n==3 mod 4
2^n==2 mod n
(I+2^r)^n==-I+2^r mod n where I is the sqrt(-1)
gcd(r,n-1)==1

Last fiddled with by paulunderwood on 2022-08-20 at 19:48

2022-09-21, 19:48   #11
paulunderwood

Sep 2002
Database er0rr

10FE16 Posts

Quote:
 Originally Posted by paulunderwood Recap: I am testing: Fermat 2-prp and (x+2^r)^(n+1)==4^r+1 where gcd(r,n-1)==1, and have reached n<4*10^14 without counterexample. Now, writing a=lift(Mod(2,n)^r) the Lucas part can be written as a Lucas test for y over y^2-2*a*y+a^2+1 which can be transformed into Euler-PRP for a^2+1 and z^((n+1)/2)==kronecker(a^2+1,n) (mod n, z^2-2*(a^2-1)/(a^2+1)*z+1). In testing this I have found that a 2-PRP plus the Lucas test on z with gcd(a^2+1,n)==1 (and gcd(r,n-1)==1) is enough without the Euler test
Taking the obvious case of r=1, then a Lucas test over y^2-4*y+5 can be transformed into a 5-Euler PRP test and a Euler-Lucas test over f(z)=z^2-6/5*z+1 (for gcd(5,n)==1). This has solutions of f(z)=0 for z=(3+-4*i)/5. The corresponding companion matrix is Z=[3/5,-4/5;1,0], the determinant of which is 4/5. Thus if n is base 2-Fermat PRP there is no need to do the base 5-Euler PRP test -- it is implied since det(Z)^k == det(Z^k) for all k.

Last fiddled with by paulunderwood on 2022-09-21 at 22:33

 Similar Threads Thread Thread Starter Forum Replies Last Post storm5510 Information & Answers 4 2019-11-30 21:32 ksteczk PrimeNet 6 2018-03-26 15:11 ozturkfa Information & Answers 7 2012-04-03 16:19 R.D. Silverman Cunningham Tables 14 2010-09-29 19:56 R.D. Silverman Cunningham Tables 11 2006-03-06 18:46

All times are UTC. The time now is 05:00.

Sun Nov 27 05:00:26 UTC 2022 up 101 days, 2:28, 0 users, load averages: 1.16, 1.15, 1.02