mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-04-30, 12:17   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

64108 Posts
Default Composite test for n == 3 mod 4

I am having difficulty finding a counterexample for n == 3 mod 4 where the test is Mod(Mod(1,n)*x+t, x^2+1)^(n+1) == 1+t^2 and where t \(\in\) {2,..,n-2}.

I have previously tested t=2 up to n<2^50.
paulunderwood is offline   Reply With Quote
Old 2020-05-01, 00:15   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×3×139 Posts
Default attempted semiprime proof

Let odd n=p.q and z=x+t and let p=3 mod 4 (and q=1 mod 4)

Then the test is \(z^n\equiv \overline{z} \pmod{n, x^2+1}\)

\(z^{p.q} \equiv \overline{z} \pmod{q, x^2+1}\)
\(z^{p} \equiv \overline{z} \pmod{q, x^2+1}\)

but \(z^{p} \equiv \overline{z} \pmod{p, x^2+1}\)

So \(z^{p} \equiv \overline{z} \pmod{n, x^2+1}\)

Hence \(z^p.\overline{z}^p \equiv z.\overline{z} \pmod{n, x^2+1}\)

So \((z.\overline{z})^{p-1} \equiv 1 \pmod{n, x^2+1}\)

Or \((t^2+1)^{p-1} \equiv 1 \pmod{n, x^2+1}\).

This must work for all t, but there are too many!

Last fiddled with by paulunderwood on 2020-05-01 at 00:16
paulunderwood is offline   Reply With Quote
Old 2020-05-01, 07:22   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D0816 Posts
Default attempted proof that all factors are 3 mod 4

Since any t can be chosen and t^2+1 has a roots if prime Q == 1 mod 4 so that (t^2+1)^j == 1 (mod Q, x^2+1) where j is non-zero i.e. 0 = 1 (mod Q, x^2+1) for precisely 2 values of t (mod Q, x^2+1). Hence all prime factors of n = p.q.r...z are of the form 3 mod 4 and are odd when counted.

Last fiddled with by paulunderwood on 2020-05-01 at 08:05
paulunderwood is offline   Reply With Quote
Old 2020-05-01, 14:51   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·139 Posts
Default An example

Suppose n=3.7.Q, where prime Q is 3 mod 4.

If Q==11, then (t^2+1)^(21) == 1 (mod 11, x^2+1)

But (t^2+1)^12 == 1 (mod 11, x^2+1)

So (t^2+1)^9 == 1 (mod 11, x^2+1)

or (t^2+1)^3 == 1 (mod 11, x^2+1)

There are too many values of t for the polynomial (t^2+1)^3-1 roots.

The same sort of thing can be done for Q=19, Q=23, Q=31 (maybe permuting the primes to find an inconsistency). Beyond Q=31, the condition (t^2+1)^21 == 1 (mod Q, x^2+1) gives rise to too few roots.

Making the "permutations" rigorous, as well as the lack of roots for larger Q and repeated primes in n is at the moment beyond me.


Last fiddled with by paulunderwood on 2020-05-01 at 14:57
paulunderwood is offline   Reply With Quote
Old 2020-05-01, 18:02   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

64108 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I am having difficulty finding a counterexample for n == 3 mod 4 where the test is Mod(Mod(1,n)*x+t, x^2+1)^(n+1) == 1+t^2 and where t \(\in\) {2,..,n-2}.
I actually ran with our expoentiating by n+1.

All else that followed is rubbish.

Last fiddled with by paulunderwood on 2020-05-01 at 18:03
paulunderwood is offline   Reply With Quote
Old 2020-05-02, 20:04   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D0816 Posts
Default improved test

This is a test for n == 3 mod 4:

gcd(t^3-t,n)==1
Mod(t,n)^(n-1)==1
Mod(Mod(1,n)*x+t,x^2+1)^(n+1)==t^2+1

This seems to work for any suitable t.

I am currently testing Carmichael numbers = 3 mod 4.
paulunderwood is offline   Reply With Quote
Old 2020-05-03, 13:53   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×72×17 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
This is a test for n == 3 mod 4:

gcd(t^3-t,n)==1
Mod(t,n)^(n-1)==1
Mod(Mod(1,n)*x+t,x^2+1)^(n+1)==t^2+1

This seems to work for any suitable t.

I am currently testing Carmichael numbers = 3 mod 4.
I note that with t = 2, this is very similar to a BPSW test -- n is a (weak) Fermat pseudoprime to the base 2, and a Lucas-type pseudoprime with D = -4. (This D seems not to be generally used in BPSW tests, though.)
Dr Sardonicus is offline   Reply With Quote
Old 2020-05-03, 14:10   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×3×139 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
I note that with t = 2, this is very similar to a BPSW test -- n is a (weak) Fermat pseudoprime to the base 2, and a Lucas-type pseudoprime with D = -4. (This D seems not to be generally used in BPSW tests, though.)
Thanks for your comments.

I have reached Carmichael numbers (3 mod 4) up to 3,411,338,491. Most Carmichael numbers are 1 mod 4.

I will next run the CRT routine by David Broadhurst against the test.

Also I will test with the combined conditions:
Mod(Mod(1,n)*t*(x+t),x^2+1)^(n+1) == t^2*(t^2+1)
paulunderwood is offline   Reply With Quote
Old 2020-05-03, 23:16   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×3×139 Posts
Default

I ran the script:

Code:
{tst(n,a)=kronecker(-1,n)==-1&&gcd(a^3-a,n)==1&&
Mod(a,n)^(n-1)==1&&
Mod(Mod(1,n)*(x+a),x^2+1)^(n+1)==a^2+1;} 

{tst1(p,q)=local(n=p*q,u=[]);
for(a=3,p-3,if((n%(p-1)==1)||
Mod(a,p)^(n-1)==1&&
Mod(Mod(1,p)*(L+a),L^2+1)^(n+1)==a^2+1,
u=concat(u,a)));Mod(u,p);}

{tst2(p,q)=local(n=p*q,up,uq,a,V=[]);
up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq,
for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
if(tst(n,a),V=concat(V,a))))));V=vecsort(V);
if(#V,print([n,V[1]]));V;}

{forprime(p=7,40000,for(k=4,6,q=1+2*k*(p-1);
if(ispseudoprime(q),tst2(p,q))));
print("\\\\ "round(gettime/1000)" seconds");}
with the results:

Code:
[79786523, 1056446]
[609451151, 20725036]
[620715499, 10405742]
[918023891, 12289481]
[1094554151, 47192161]
[1608751523, 63997807]
[1797382823, 68389811]
[2086618571, 26185483]
[2268928751, 46979685]
[2142871459, 24856981]
[1894955311, 101084388]
[3028586471, 78670828]
[3056100623, 97597057]
[3894053311, 478976896]
[7430285479, 601296308]
[9347580631, 137503381]
[15128574011, 855709667]
[17319375071, 169377571]
\\ 481 seconds
Back to the drawing board. It amazes me that for n == 3 mod 4 the test (x+2)^(n+1) == 5 (mod n, x^2+1) is so good. I plan to start collecting 5-PRPs for n == 3 mod 4 at a future time.
paulunderwood is offline   Reply With Quote
Old 2020-06-28, 18:28   #10
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

13·23 Posts
Post

A quick improvement to the test:

For n = 3 mod 4, we have:

1) Find b = t^2 + 1 such that Jacobi(b, n)==1
2) gcd(t^3 - t, n)==1
3) Compute u*x + v = (x + t)^((n + 1)/2) mod (n, x^2 + 1)
4) Verify (x + t)^(n + 1) == b mod (n, x^2 + 1)

If u == 0 mod n, then n is a b-SPRP. To show this, in (3), if u == 0 mod n, then v is a proper square root of b mod n, so v^2 - b = 0 mod n, implying for all prime factors q | n, b is a quadratic residue mod n, in which case, the order of b mod q is odd, so

b^((n-1)/2) == 1 mod n.

I think, there is something similar if Jacobi(b, n)==-1, although u may not be 0 in step 3.
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I found the primality test, there seems to be no composite numbers that pass the test sweety439 sweety439 7 2020-02-11 19:49
Composite PRP ATH Math 23 2019-05-10 14:50
quadratic composite test paulunderwood Math 90 2012-05-06 21:39
The composite conjecture Carl Fischbach Miscellaneous Math 8 2010-07-02 08:03
F10,21=10^(2^21)+1 is composite Shaopu Lin Factoring 2 2004-10-31 13:48

All times are UTC. The time now is 06:42.

Wed Aug 12 06:42:08 UTC 2020 up 26 days, 2:28, 1 user, load averages: 0.86, 1.28, 1.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.