mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-07-17, 16:29   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·52·29 Posts
Default 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
paulunderwood is offline   Reply With Quote
Old 2022-07-17, 20:34   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

435010 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-07-18, 18:26   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

435010 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

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
paulunderwood is offline   Reply With Quote
Old 2022-07-18, 23:48   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·52·29 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

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
paulunderwood is offline   Reply With Quote
Old 2022-07-19, 18:03   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

435010 Posts
Default

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<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,n-1)==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))))))}
where V is a list of base 2 pseudoprimes

Testing has reached 1.5e12

I have now added Mod(det,n)^((n-1)/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 2022-07-20 at 00:32
paulunderwood is offline   Reply With Quote
Old 2022-08-18, 15:26   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·52·29 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-08-19, 04:47   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10FE16 Posts
Default

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.
paulunderwood is offline   Reply With Quote
Old 2022-08-19, 14:18   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10FE16 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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?
paulunderwood is offline   Reply With Quote
Old 2022-08-19, 19:23   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10FE16 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-08-20, 19:47   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·52·29 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2022-09-21, 19:48   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10FE16 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sigma parameter in ecm storm5510 Information & Answers 4 2019-11-30 21:32
PrimeNet error 7: Invalid parameter ksteczk PrimeNet 6 2018-03-26 15:11
changing mprime's WorkerThreads parameter? ozturkfa Information & Answers 7 2012-04-03 16:19
Parameter Underestimation R.D. Silverman Cunningham Tables 14 2010-09-29 19:56
ECM Work and Parameter Choices 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

Powered by vBulletin® Version 3.8.11
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.

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