20200430, 12:17  #1 
Sep 2002
Database er0rr
6566_{8} 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,..,n2}.
I have previously tested t=2 up to n<2^50. 
20200501, 00:15  #2 
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})^{p1} \equiv 1 \pmod{n, x^2+1}\) Or \((t^2+1)^{p1} \equiv 1 \pmod{n, x^2+1}\). This must work for all t, but there are too many! Last fiddled with by paulunderwood on 20200501 at 00:16 
20200501, 07:22  #3 
Sep 2002
Database er0rr
6566_{8} 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 nonzero 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 20200501 at 08:05 
20200501, 14:51  #4 
Sep 2002
Database er0rr
3446_{10} 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)^31 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 20200501 at 14:57 
20200501, 18:02  #5  
Sep 2002
Database er0rr
2×1,723 Posts 
Quote:
All else that followed is rubbish. Last fiddled with by paulunderwood on 20200501 at 18:03 

20200502, 20:04  #6 
Sep 2002
Database er0rr
2·1,723 Posts 
improved test
This is a test for n == 3 mod 4:
gcd(t^3t,n)==1 Mod(t,n)^(n1)==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. 
20200503, 13:53  #7 
Feb 2017
Nowhere
2×1,787 Posts 
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 Lucastype pseudoprime with D = 4. (This D seems not to be generally used in BPSW tests, though.)

20200503, 14:10  #8  
Sep 2002
Database er0rr
2·1,723 Posts 
Quote:
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) 

20200503, 23:16  #9 
Sep 2002
Database er0rr
2×1,723 Posts 
I ran the script:
Code:
{tst(n,a)=kronecker(1,n)==1&&gcd(a^3a,n)==1&& Mod(a,n)^(n1)==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,p3,if((n%(p1)==1) Mod(a,p)^(n1)==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*(p1); if(ispseudoprime(q),tst2(p,q)))); print("\\\\ "round(gettime/1000)" seconds");} 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 
20200628, 18:28  #10 
"Sam"
Nov 2016
474_{8} 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 bSPRP. 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^((n1)/2) == 1 mod n. I think, there is something similar if Jacobi(b, n)==1, although u may not be 0 in step 3. 
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  20200211 19:49 
Composite PRP  ATH  Math  23  20190510 14:50 
quadratic composite test  paulunderwood  Math  90  20120506 21:39 
The composite conjecture  Carl Fischbach  Miscellaneous Math  8  20100702 08:03 
F10,21=10^(2^21)+1 is composite  Shaopu Lin  Factoring  2  20041031 13:48 