20180922, 11:18  #1 
Sep 2002
Database er0rr
3·1,327 Posts 
Frobenius and semiprime testing
Ya'll know that for a^gcd(n1,eulerphi(n)) == 1 (mod n) for all n and gcd(a,n)==1.
Now restrict n to being an odd semiprime. Let Fr(x) = x^2P*x+Q with jacobi(P^24*Q,n)==1, with gcd(P*Q)=1. Then x^(n+1) = 1 (mod n, Fr(x)). This is equivalent to the two tests: Mod(Q,n)^(n1)==1 and Mod(Mod(1,n)*x,x^2R*x+1)^(n+1)==1 where R=P^2/Q2. Let n=p*q and D=R^24. Then jacobi(p*q,D)==1. Without loss of generality let jacobi(p,D)==1, so that jacobi(q,D)==1. We can see that: x^(p*q+1) == 1 (n, x^2R*x+1) x^(q+1) == 1 (mod p, x^2R*x+1) and we know x^(q+1) == 1 (mod p, x^2R*x+1) Similarly x^(p1) == 1 (mod q, x^2R*x+1) and x^(p1) == 1 (mod q, x^2R*x+1) So x^(p1) == 1 (mod n, x^2R*x+1) and x^(q+1) == (mod n, x^2R*x+1) Multiplying together: x^(p1+q+1) == 1 mod(n, x^2R*x+1) I.e. x^(p+q) == 1 (mod n, x^2R*x+1). Thus: x^gcd(n+1,p+q) == 1 (mod p*q, x^2R*x+1) (**) Recalling that e = eulerphi(p*q) = (n+1)  (p+q). We have two exponent values to calculate to test Fr(x): g = gcd(n1, e) and h = gcd(n+1, e). For verification of my test I want the minimal R such that jacobi(R^24,n) == 1. Since it takes C times as long to perform an iteration of leftright binary exponentiation iteration on (**) than one for Mod(Q,n)^g == 1, where C~= 2.4. Thus during verification of my test for semiprimes I can make an intelligent decision whether to test Frobenius+Fermat or Femat+Frobenius. Luckly, g and h are very small indeed! 
20180922, 12:21  #2 
Sep 2002
Database er0rr
3·1,327 Posts 
By testing some semi primes, the magic ratio of whether to test Fermat or Frobenius first is 1. So min(g,h) is best
Last fiddled with by paulunderwood on 20180922 at 12:55 
20180922, 17:32  #3 
Sep 2002
Database er0rr
3·1,327 Posts 
I have also considered Carmichael numbers of the form:
p=6*b+1; q=12*b+1; r=18*b+1. If kronecker(D,n) == 1 there are 2 cases: 1 nonresidue and 2 residues or 3 nonresidues. I will attempt here the first case, assuming r is the nonresidue Let c(b) = p*q*r; f(b) = c(b)+1; and g(b) = (p1)*(q1)*(r+1). Then we have x^g(b) == 1 (mod n, x^2R*x+1) if jacobi(R^24,n). But my test requires x^f(b) == 1 (mod n, x^2R*x+1). So x^gcd(f(b),g(b)) == 1 (mod n, x^2R*x+1). I have calculated for values of b and the gcd seems to either 2 or 10. Can you prove this? 
20180922, 20:51  #4 
Sep 2002
Database er0rr
3×1,327 Posts 
Clearly if the gcd is 2 there can be no solution since x^2==Rx1==1 implies Rx==2. So (P^2/Q2)x would equal 2. I.e. P^2/Q == 2(1+x) leading to x=P^2/2/Q1, But x is conjoined. So that leaves only Carmichael numbers with gcd(f(b),g(b))==10.

20180923, 02:41  #5 
Sep 2002
Database er0rr
3×1,327 Posts 
Recap: c(b) = p*q*r = (6*b+1)*(12*b+1)*(18*b+1). If jacobi(D,q)==1 and jacobi(D,p)==1 and jacobi(D,r)==1, then gcd(f(b),g(b)) is always 2 (proof?) and therefore there is no pseudoprime.
Whatever the chosen R is, the gcd is in {2,5,10,7,14,70} and the maximum seems to be 70: x^70 == 1 (Mod c(b), x^2R*x+1). Last fiddled with by paulunderwood on 20180923 at 02:42 
20180925, 11:34  #6 
Sep 2002
Database er0rr
3×1,327 Posts 
The "hybrid" version of my test tests (x+1)^(n+1) == a + 2 (mod n, x^2a*x+1) where a > 2 and is minimal (and for a=0 or 1 test (x+2)^(n+1)=2*a+5 (mod n, x^2a*x+1)).
That is P==Q==a+2 and so R=a. I think I need to maximally search through L(n) := log(n) *(log(log(n)) possible R to find one for which jacobi(R^24,n)==1. For the above Carmichael number form x^(70) == 1 (mod x^2R*x+1) That is about R^35 ~= 1 (mod n). But L(n)^35 is smaller than p=6*b+1 for sufficiently large b. Last fiddled with by paulunderwood on 20180925 at 12:09 
20180925, 14:04  #7 
Sep 2002
Database er0rr
3·1,327 Posts 
I think the above argument can be extended to all of Jack Chernick's Carmichael function given in (8) of "On Fermat's simple theorem". For example, for c(b) = (6*b+1)*(12*b+1)*(18*b+1)*(36*b+1) I need only test x^166==1 (mod n, x^2a*x+1) and eventually L_max(c(b))^83 will be less than (6*p+1).
Last fiddled with by paulunderwood on 20180925 at 14:12 
20180926, 01:13  #8 
Sep 2002
Database er0rr
3981_{10} Posts 
Am I right to think all families of Carmichael numbers are of the form:
If so then the above argument for L_max(c(b)) can be extended to them: x^{G*gcd(f/G,polresultant(f/G,(fg)/G))} == 1 (mod c(b), x^2a*x+1) where G = gcd(f,g). The above exponent must be calculated over all combinations of factors of c(b) which makes jacobi(D,c(b)) == 1 Thanks to Dr Sardonicus for enlightening me about resultants. Last fiddled with by paulunderwood on 20180926 at 01:51 
20180926, 15:22  #9 
Sep 2002
Database er0rr
111110001101_{2} Posts 
I am going to stick my neck out here...
Let be a product of s increasing odd distinct factors where Let f(b) = n(b)+1 and Let H = gcd(f(b), polresultant(fg,f)). Then I claim I need only test x^(2*H) == 1 (mod n(b), x^2a*x+1) where jacobi(a^24,n(b))==1 (and 2<a<(n(b)2) and Q^n(b)==Q mod n(b)). Furthermore for sufficiently large b. So far my arguments have been sketchy and this last idea a guess! Last fiddled with by paulunderwood on 20180926 at 15:46 
20180927, 10:11  #10 
Sep 2002
Database er0rr
3×1,327 Posts 
Keeping the definitions for n(b), f(b) and g(b) in my previous post, but letting:
H = gcd(f(b), polresultant(f,g)) then computer experiments (n(b)<100,000 and all 2<a<n2) shows that x^H==1 (mod n, x^2a*x+1) if x^f(b)==1 (mod n, x^2a*x+1) with jacobi(a^24,n)==1. 
20180927, 20:14  #11 
Sep 2002
Database er0rr
3×1,327 Posts 
I now have a formula for all odd (nonsquare) n, not just square free n:
Let: Then implies where Jacobi(a^24,n)==1. Furthermore, there is no need to verify the hybrid part my "hybrid" test for odd numbers given sufficiently large b. Last fiddled with by paulunderwood on 20180927 at 20:51 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Semiprime factorization conjecture  Alberico Lepore  Alberico Lepore  7  20180216 08:27 
Probability that n is a semiprime or prime  carpetpool  Miscellaneous Math  27  20170119 21:00 
Prime testing software suggestions please.  ishkibibble  Conjectures 'R Us  15  20130314 08:41 
How does this whole primetesting thing work?  Unregistered  Software  27  20040913 21:35 
Semiautomated P1 testing  GP2  Marin's Mersennearies  2  20030929 19:01 