Loading ...
Sorry, an error occurred while loading the content.

30% less a few bits

Expand Messages
  • d.broadhurst@open.ac.uk
    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.

      David Broadhurst
    • Chris Nash
      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.