mersenneforum.org Composite test for n == 3 mod 4
 Register FAQ Search Today's Posts Mark Forums Read

 2020-04-30, 12:17 #1 paulunderwood     Sep 2002 Database er0rr 2×1,723 Posts 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.
 2020-05-01, 00:15 #2 paulunderwood     Sep 2002 Database er0rr 2×1,723 Posts 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
 2020-05-01, 07:22 #3 paulunderwood     Sep 2002 Database er0rr 2·1,723 Posts 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
 2020-05-01, 14:51 #4 paulunderwood     Sep 2002 Database er0rr 2×1,723 Posts 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
2020-05-01, 18:02   #5
paulunderwood

Sep 2002
Database er0rr

2×1,723 Posts

Quote:
 Originally Posted by paulunderwood 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

 2020-05-02, 20:04 #6 paulunderwood     Sep 2002 Database er0rr D7616 Posts 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.
2020-05-03, 13:53   #7
Dr Sardonicus

Feb 2017
Nowhere

22·5·179 Posts

Quote:
 Originally Posted by paulunderwood 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.)

2020-05-03, 14:10   #8
paulunderwood

Sep 2002
Database er0rr

2·1,723 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.)

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)

 2020-05-03, 23:16 #9 paulunderwood     Sep 2002 Database er0rr 65668 Posts 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.
 2020-06-28, 18:28 #10 carpetpool     "Sam" Nov 2016 1001111002 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 7 2020-02-11 19:49 ATH Math 23 2019-05-10 14:50 paulunderwood Math 90 2012-05-06 21:39 Carl Fischbach Miscellaneous Math 8 2010-07-02 08:03 Shaopu Lin Factoring 2 2004-10-31 13:48

All times are UTC. The time now is 01:33.

Thu Oct 29 01:33:52 UTC 2020 up 48 days, 22:44, 1 user, load averages: 1.16, 1.50, 1.69