mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2018-09-22, 11:18   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·1,049 Posts
Default 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!
paulunderwood is offline   Reply With Quote
Old 2018-09-22, 12:21   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,049 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2018-09-22, 17:32   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,049 Posts
Default

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?
paulunderwood is offline   Reply With Quote
Old 2018-09-22, 20:51   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

C4B16 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
paulunderwood is offline   Reply With Quote
Old 2018-09-23, 02:41   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·1,049 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2018-09-25, 11:34   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·1,049 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2018-09-25, 14:04   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,049 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2018-09-26, 01:13   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·1,049 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2018-09-26, 15:22   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,049 Posts
Default

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<a<(n(b)-2) and Q^n(b)==Q mod n(b)).

Furthermore L_{max}^H < k_1*b+1 for sufficiently large b.

So far my arguments have been sketchy and this last idea a guess!

Last fiddled with by paulunderwood on 2018-09-26 at 15:46
paulunderwood is offline   Reply With Quote
Old 2018-09-27, 10:11   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

C4B16 Posts
Default

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<n-2) shows that x^H==1 (mod n, x^2-a*x+1) if x^f(b)==1 (mod n, x^2-a*x+1) with jacobi(a^2-4,n)==-1.
paulunderwood is offline   Reply With Quote
Old 2018-09-27, 20:14   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1100010010112 Posts
Default

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
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Semi-prime factorization conjecture Alberico Lepore Alberico Lepore 7 2018-02-16 08:27
Probability that n is a semi-prime or prime carpetpool Miscellaneous Math 27 2017-01-19 21:00
Prime testing software suggestions please. ishkibibble Conjectures 'R Us 15 2013-03-14 08:41
How does this whole prime-testing thing work? Unregistered Software 27 2004-09-13 21:35
Semi-automated P-1 testing GP2 Marin's Mersenne-aries 2 2003-09-29 19:01

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

Thu Apr 9 11:20:54 UTC 2020 up 15 days, 8:53, 1 user, load averages: 1.63, 1.42, 1.31

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.