- 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.

David Broadhurst - Hi folks

>Modified KP test with additional square tests

...cut...

>The practical point of this note is to allow OpenPfgw to write a

Nicely 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

else :)

Chris