 mersenneforum.org 3 mod 4 with free parameter
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2022-07-17, 16:29 #1 paulunderwood   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^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 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^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

102778 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

3·1,429 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 3·1,429 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 3×1,429 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 3·1,429 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

3·1,429 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 3×1,429 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

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

10000101111112 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   Thread Tools Show Printable Version Email this Page 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 11:25.

Mon Oct 3 11:25:35 UTC 2022 up 46 days, 8:54, 0 users, load averages: 0.88, 0.97, 1.03

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔