30% less a few bits
- Modified KP test with additional square tests
Let N=F*R+1 with gcd(F,R)=1 and R>F^2.
Suppose that the BLS tests establish
that every factor of N is 1 mod F.
Let c1 be the unique integer in [1,F-1]
such that c4=(R-c1)/F is an integer.
Now test that
is not a square for any t in [0,T] with T>0.
[Note that KP set T=5. We are more general.]
Now *modify* the KP cubic algorithm
by taking u/v to be the continued
fraction convergent to c1/F with
maximal v < F^(1/3) [NOT F^2/sqrt(N), pace KP]
Suppose that we construct the cubic
P(X) = v*X^3 + (u*F-c1*v)*X^2 + (c4*v-d*F+u)*X - d
and verify that none of its roots is an integer.
Then N is prime, if
F^(1/3)/6 > T > 3*N/F^(10/3)
Following the method of CP 4.1.6, suppose that
N were not prime, but instead of the form
N=(a1*F+1)*(a2*F+1) with a2>=a1>0.
Let t = c4-a1*a2
Let M = a1*(u+t*v)-c4*v/F
Then we need to show that |M| < 1/2.
First observe that
a1+a2 = c1+t*F > (T+1)*F
since c1>0 and t>T. Now note that
a1 < N/F^3 < F^(2/3)/18 < F
and hence that
a2 > T*F.
Next observe that
a1 < c4/a2 < (N/F^2)/(T*F) < F(1/3)/3.
|M| < M1 + M2 + M3
M1 = a1*v*|u/v-c1/F| < a1/F^(1/3) < 1/3
M2 = a1^2*v/F < a1^2/F^(2/3) < 1/9
M3 = t*v/F < (N/F^3)*F^(1/3)/F < 1/18
|M| < 1/3 + 1/9 + 1/18 = 1/2
It follows that
and hence that P(a1)=0, contra hyp.
Hence N is prime.
For sufficiently large F and sufficiently small T
T > (1+sqrt(3))*N/F^(10/3)
becomes sufficient, since
1/(1+sqrt(3)) + 1/(1+sqrt(3))^2 = 1/2.
For the sake of inclusiveness, I replaced (1+sqrt(3)) by 3.
The extra 10% of T disposes of a lot of messy if statements
and allows for all T<F^(1/3)/6.
[This limit would not be reached in practice.]
The practical point of this note is to allow OpenPfgw to write a
"30% less a few bits" N-1 option: pfgw -tkpm -x.
- Hi folks
>Modified KP test with additional square tests...cut...
>The practical point of this note is to allow OpenPfgw to write aNicely done :) As David points out, the Pomerance-Konyagin algorithm is
>"30% less a few bits" N-1 option: pfgw -tkpm -x.
brute force algebra - there's little extra needed for this to get
included, and it also has the capability of the 'extra bits'. I was
going to have a look at the same thing for N-1, N+1, and combined tests
too, but I seemed to do a lot of sleeping this weekend and not a lot