## 30% less a few bits

Expand Messages
• 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
Message 1 of 2 , Jun 25, 2001
• 0 Attachment
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
(c1+t*F)^2+4*t-4*c4
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
with d=round(c4*v/F)
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)
============================

Proof:
======
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
= (a1+a2-c1)/F.
Let M = a1*(u+t*v)-c4*v/F
= a1*v*(u/v-c1/F)+(a1^2-t)*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.
Then
|M| < M1 + M2 + M3
with
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
and hence
|M| < 1/3 + 1/9 + 1/18 = 1/2
as required.
It follows that
d=round(c4*v/F)=a1*(u+t*v)
and hence that P(a1)=0, contra hyp.
Hence N is prime.

Notes:
======
For sufficiently large F and sufficiently small T
the bound
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 ... Nicely done :) As David points out, the Pomerance-Konyagin algorithm is brute force algebra - there s little extra needed for this to get
Message 2 of 2 , Jun 26, 2001
• 0 Attachment
Hi folks

>Modified KP test with additional square tests
...cut...
>The practical point of this note is to allow OpenPfgw to write a
>"30% less a few bits" N-1 option: pfgw -tkpm -x.

Nicely done :) As David points out, the Pomerance-Konyagin algorithm is
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
else :)

Chris
Your message has been successfully submitted and would be delivered to recipients shortly.