mersenneforum.org > Math Frobenius and semi-prime testing
 Register FAQ Search Today's Posts Mark Forums Read

 2018-09-22, 11:18 #1 paulunderwood     Sep 2002 Database er0rr 3·1,327 Posts Frobenius and semi-prime testing Ya'll know that for a^gcd(n-1,eulerphi(n)) == 1 (mod n) for all n and gcd(a,n)==1. Now restrict n to being an odd semi-prime. Let Fr(x) = x^2-P*x+Q with jacobi(P^2-4*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)^(n-1)==1 and Mod(Mod(1,n)*x,x^2-R*x+1)^(n+1)==1 where R=P^2/Q-2. Let n=p*q and D=R^2-4. 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^2-R*x+1) x^(q+1) == 1 (mod p, x^2-R*x+1) and we know x^(q+1) == 1 (mod p, x^2-R*x+1) Similarly x^(p-1) == 1 (mod q, x^2-R*x+1) and x^(p-1) == 1 (mod q, x^2-R*x+1) So x^(p-1) == 1 (mod n, x^2-R*x+1) and x^(q+1) == (mod n, x^2-R*x+1) Multiplying together: x^(p-1+q+1) == 1 mod(n, x^2-R*x+1) I.e. x^(p+q) == 1 (mod n, x^2-R*x+1). Thus: x^gcd(n+1,p+q) == 1 (mod p*q, x^2-R*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(n-1, e) and h = gcd(n+1, e). For verification of my test I want the minimal R such that jacobi(R^2-4,n) == -1. Since it takes C times as long to perform an iteration of left-right binary exponentiation iteration on (**) than one for Mod(Q,n)^g == 1, where C~= 2.4. Thus during verification of my test for semi-primes I can make an intelligent decision whether to test Frobenius+Fermat or Femat+Frobenius. Luckly, g and h are very small indeed!
 2018-09-22, 12:21 #2 paulunderwood     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 2018-09-22 at 12:55
 2018-09-22, 17:32 #3 paulunderwood     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 non-residue and 2 residues or 3 non-residues. I will attempt here the first case, assuming r is the non-residue Let c(b) = p*q*r; f(b) = c(b)+1; and g(b) = (p-1)*(q-1)*(r+1). Then we have x^g(b) == 1 (mod n, x^2-R*x+1) if jacobi(R^2-4,n). But my test requires x^f(b) == 1 (mod n, x^2-R*x+1). So x^gcd(f(b),g(b)) == 1 (mod n, x^2-R*x+1). I have calculated for values of b and the gcd seems to either 2 or 10. Can you prove this?
2018-09-22, 20:51   #4
paulunderwood

Sep 2002
Database er0rr

3×1,327 Posts

Quote:
 Originally Posted by paulunderwood I have calculated for values of b and the gcd seems to either 2 or 10. Can you prove this?
Clearly if the gcd is 2 there can be no solution since x^2==Rx-1==1 implies Rx==2. So (P^2/Q-2)x would equal 2. I.e. P^2/Q == 2(1+x) leading to x=P^2/2/Q-1, But x is conjoined. So that leaves only Carmichael numbers with gcd(f(b),g(b))==10.

 2018-09-23, 02:41 #5 paulunderwood     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^2-R*x+1). Last fiddled with by paulunderwood on 2018-09-23 at 02:42
 2018-09-25, 11:34 #6 paulunderwood     Sep 2002 Database er0rr 3×1,327 Posts The "hybrid" version of my test tests (x+1)^(n+1) == a + 2 (mod n, x^2-a*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^2-a*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^2-4,n)==-1. For the above Carmichael number form x^(70) == 1 (mod x^2-R*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 2018-09-25 at 12:09
 2018-09-25, 14:04 #7 paulunderwood     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^2-a*x+1) and eventually L_max(c(b))^83 will be less than (6*p+1). Last fiddled with by paulunderwood on 2018-09-25 at 14:12
 2018-09-26, 01:13 #8 paulunderwood     Sep 2002 Database er0rr 398110 Posts Am I right to think all families of Carmichael numbers are of the form: $\prod_k{k*b+1}$ If so then the above argument for L_max(c(b)) can be extended to them: x^{G*gcd(f/G,polresultant(f/G,(f-g)/G))} == 1 (mod c(b), x^2-a*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 2018-09-26 at 01:51
 2018-09-26, 15:22 #9 paulunderwood     Sep 2002 Database er0rr 1111100011012 Posts I am going to stick my neck out here... Let $n(b)=\prod_{i\le s}(k_i*b+1)$ be a product of s increasing odd distinct factors where $gcd(k_1,..,k_s)=1$ Let f(b) = n(b)+1 and $g(b)=\prod_{i\le s}(k_i*b+2)$ Let H = gcd(f(b), polresultant(f-g,f)). Then I claim I need only test x^(2*H) == 1 (mod n(b), x^2-a*x+1) where jacobi(a^2-4,n(b))==-1 (and 2
 2018-09-27, 10:11 #10 paulunderwood     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
 2018-09-27, 20:14 #11 paulunderwood     Sep 2002 Database er0rr 3×1,327 Posts I now have a formula for all odd (non-square) n, not just square free n: Let: $n(b)=\prod_{i\le s}(k_i b+1)^{e_i}$ $gcd(k_1,\ldots,k_s)=1$ $f(b)=n(b)+1$ $g(b)=\prod_{i\le s}(k_i b+2)^{e_i}$ $H=gcd(f(b),polresultant(f,g))$ Then $x^{f(b)}==1 \pmod{n, x^2-ax+1}$ implies $x^H==1 \pmod{n, x^2-ax+1}$ where Jacobi(a^2-4,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 2018-09-27 at 20:51

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 7 2018-02-16 08:27 carpetpool Miscellaneous Math 27 2017-01-19 21:00 ishkibibble Conjectures 'R Us 15 2013-03-14 08:41 Unregistered Software 27 2004-09-13 21:35 GP2 Marin's Mersenne-aries 2 2003-09-29 19:01

All times are UTC. The time now is 11:19.

Fri Jan 21 11:19:25 UTC 2022 up 182 days, 5:48, 0 users, load averages: 1.34, 1.31, 1.28