20220717, 16:29  #1 
Sep 2002
Database er0rr
3·1,429 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^22*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^3a,n)==1&& Mod(2,n)^(n1)==1&& Mod(a,n)^(n1)==1&& Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;} Last fiddled with by paulunderwood on 20220717 at 17:38 
20220717, 20:34  #2 
Sep 2002
Database er0rr
3×1,429 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^3a,n)==1&& Mod(2,n)^(n1)==1&& Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;} Last fiddled with by paulunderwood on 20220717 at 20:50 
20220718, 18:26  #3 
Sep 2002
Database er0rr
10277_{8} Posts 
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

20220718, 23:48  #4  
Sep 2002
Database er0rr
3·1,429 Posts 
Quote:
Note n divides 2^(n1)1. gcd(a^21,n)==1 ==> gcd(2^(2*r)1,2^(n1)1)==1 ==> gcd(2*r,n1)==2 if gcd(r,(n1)/2)==1. Hence the required condition gcd(2,n1)==2 which is met for n==3 mod 4. Last fiddled with by paulunderwood on 20220719 at 02:53 

20220719, 18:03  #5 
Sep 2002
Database er0rr
3·1,429 Posts 
Let z=znorder(Mod(2,n)).
Then [2^(zr),1;1,2^(zr)]^(n+1) == 4^(zr)+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*(n1)) 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<r<(z+1)/2, Thus speeding up the verification program by a factor of two: Code:
{for(v=1,#V,n=V[v]; if(n%4==3,z=znorder(Mod(2,n));print([v,n,z]); for(r=1,(z+1)/2, if(gcd(r,n1)==1,a=lift(Mod(2,n)^r); if(Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1, print([n,a,r,z]);break(2))))))} Testing has reached 1.5e12 I have now added Mod(det,n)^((n1)/2)==kronecker(det,n) where det=a^2+1, to speed it up some more. Testing now at 2.7e12. Last fiddled with by paulunderwood on 20220720 at 00:32 
20220818, 15:26  #6 
Sep 2002
Database er0rr
3×1,429 Posts 
Recap: I am testing: Fermat 2prp and (x+2^r)^(n+1)==4^r+1 where gcd(r,n1)==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^22*a*y+a^2+1 which can be transformed into EulerPRP for a^2+1 and z^((n+1)/2)==kronecker(a^2+1,n) (mod n, z^22*(a^21)/(a^2+1)*z+1). In testing this I have found that a 2PRP plus the Lucas test on z with gcd(a^2+1,n)==1 (and gcd(r,n1)==1) is enough without the Euler test Last fiddled with by paulunderwood on 20220818 at 15:28 
20220819, 04:47  #7 
Sep 2002
Database er0rr
3·1,429 Posts 
A small observation: If a number n==3 mod 4 is Fermat 2PRP then 2^(n1)==1 mod n. If z is the multiplicative order of 2 mod n, then z divides n1. Also (x+2^z) == x+1 mod n. Furthermore, (x+1)^(n+1) == 2 (mod n, x^2+1) is equivalent to a Fermat 2PRP test. Neat, eh? And gcd(r,n1) implies gcd(r,z)==1.

20220819, 14:18  #8  
Sep 2002
Database er0rr
3·1,429 Posts 
Quote:
Does anyone care to complete the proof of the test? 

20220819, 19:23  #9 
Sep 2002
Database er0rr
3×1,429 Posts 
Summarizing the two cases:
n%8=3 :: 2^((n1)/2) == 1 mod n :: z/2 is odd :: two solutions exist: z and z/2 n%8=7 :: 2^((n1)/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 2PRP plus (x+2^r)^(n+1) == 4^r+1 (mod n, x^2+1) with gcd(r,n1) == 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 2PRP + the test for (x+2)? Last fiddled with by paulunderwood on 20220820 at 17:47 Reason: noting z/2 is odd 
20220820, 19:47  #10  
Sep 2002
Database er0rr
10BF_{16} Posts 
Quote:
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,n1)==1 Last fiddled with by paulunderwood on 20220820 at 19:48 

20220921, 19:48  #11  
Sep 2002
Database er0rr
1000010111111_{2} Posts 
Quote:
Last fiddled with by paulunderwood on 20220921 at 22:33 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sigma parameter in ecm  storm5510  Information & Answers  4  20191130 21:32 
PrimeNet error 7: Invalid parameter  ksteczk  PrimeNet  6  20180326 15:11 
changing mprime's WorkerThreads parameter?  ozturkfa  Information & Answers  7  20120403 16:19 
Parameter Underestimation  R.D. Silverman  Cunningham Tables  14  20100929 19:56 
ECM Work and Parameter Choices  R.D. Silverman  Cunningham Tables  11  20060306 18:46 