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

Lucas tests with Fermat tests for free

Expand Messages
  • djbroadhurst
    ... Paul Underwood s preprint at http://www.mersenneforum.org/showpost.php?p=298027&postcount=44 has a rather neat observation in Section 4, which is all one
    Message 1 of 33 , May 29 2:40 PM
      --- In primenumbers@yahoogroups.com,
      "paulunderwooduk" <paulunderwood@> wrote:

      > Please see my draft paper

      Paul Underwood's preprint at
      http://www.mersenneforum.org/showpost.php?p=298027&postcount=44
      has a rather neat observation in Section 4, which is all one
      really needs to read to understand how Paul can do in
      2 selfridges what takes BPSW 1 + 2 selfridges and takes
      Grantham 2 + 1 selfridges, using the Frobenius method of
      Crandall and Pomerance.

      Shorn of any references to matrices, Paul's proposal is to
      test an odd non-square target N for probable primality using
      a Frobenius test based on the Lucas sequence with
      P = A*x + 2*B and Q = A*B*x + A^2 + B^2, where A > 0 and B
      are small integers and x is the smallest non-negative
      integer such that kronecker(x^2-4,N) = -1. Specifically, Paul
      has found that with A = 1 and B = 2 there are no pseudoprimes
      with N < 4*10^12.

      Crandall and Pomerance show, in Algorithm 3.5.9, how to
      accomplish a Lucas test in 2 selfridges and then strengthen
      it to a Frobenius test at the expense of a 3rd selfridge.
      (Note that CP denote the Lucas parameters (P,Q) by (a,b),
      which I avoid doing, since Paul uses the symbols (a,b) for
      a different purpose.}

      A Frobenius test involves modular exponentiation of

      z mod (N, z^2 - P*z + Q)

      In Paul's case this turns into modular exponentiation of

      (A*lambda + B) mod (N, lambda^2 - x*lambda + 1)

      Using left-right binary exponentiation, the cost, at large
      N, is dominated by squaring (a*lambda + b) where (a,b) are
      large integers, mod N, from the previous step. (The cost of
      also multiplying by (A*lambda + B), when the bit is odd, is
      asymptotically negligible, in comparison, since A and B are
      assumed to be small integers.)

      Now comes the neat bit: the cost of computing

      (a*lambda + b)^2 = a*(a*x + 2*b)*lambda + (b - a)*(b + a)
      mod (N, lambda^2 - x*lambda + 1) ...... [*]

      is dominated by only 2 multiplications of large numbers,
      a*(a*x + 2*b) and (b - a)*(b + a), mod N, since x is small.
      Defining a "selfridge" as log(N)/log(2) times the cost of a
      modular multiplication of two large numbers of order N, this
      is clearly a 2-selfridge test. Yet it accomplishes not only
      a Lucas test but also a Fermat test, Q^(N-1) = 1 mod N,
      where Q = A*B*x + A^2 + B^2 is 2*x + 5 in Paul's preferred
      case, with A = 1 and B = 2.

      Like many good ideas, Paul's modular equation [*], above, is
      both simple and effective. I think that it might usefully be
      decoupled from the rest of the preprint in a short (and also
      matrix-free) note along the lines "Lucas tests with Fermat
      tests for free", with due reference to C&P's 2 + 1 selfridge
      Frobenius method, whose Fermat test was not for free.

      Caveat lector: the BPSW test with, 1 + 2 selfridges, will
      beat Paul's 2 selfridge test, when applied to a large number
      of random targets of size N, since the BPSW 2-selfridge
      second part is invoked only in a fraction O(1/log(N)) of the
      cases that the initial 1-selfridge Fermat test fails to
      detect a composite.

      Thus there should be no suggestion that folk may benefit by
      switching from BPSW to Paul's method, when processing large
      batches. Paul acknowledges this in his preprint, by frankly
      admitting that his testing was a 1 + 2 selfridge process,
      with filtering by the Fermat test in base Q = 2*x + 5. If
      this did not detect a composite, he then performed the
      2-selfridge Frobenius test that amounts to a Lucas test plus
      the Fermat test that he /already/ knows will work. Thus there
      is no free lunch, when batch processing.

      Moreover, as so often in such discussions, selfridge-counts
      for testing a known PRP are irrelevant in comparison with
      the much larger effort of finding that PRP, which costs,
      generically, exp(-Euler)*log(N)/log(p) selfridges, after
      sensibly sieving to a decent depth p.

      However, if one has found a probable prime N and wishes to
      tell someone else that it is a (P,Q) Frobenius probable
      prime, this may be now be achieved in 2 selfridges, with
      Paul's preferred choice P = x + 4, Q = 2*x + 5, and
      kronecker(Delta,N) = -1, where Delta = P^2 - 4*Q = x^2 - 4.

      With thanks to Paul, for his neat observation,

      David Broadhurst
    • paulunderwooduk
      ... I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings { 17.505s pfgw (3-prp) 1m1.986s
      Message 33 of 33 , Sep 21, 2012
        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
        :
        > http://tech.groups.yahoo.com/group/primenumbers/files/Articles/

        > I ran various "minimal \lambda+2" tests on Gilbert Mozzo's 20,000 digit PRP, 5890*10^19996+2^66422-3 (x=1), using a 2.4GHz core:
        > {
        > 0m32.374s pfgw64 (3-prp)
        > 1m9.876s pfgw64 -t
        > 1m53.535s pfgw64 -tp
        > 3m0.483s pfgw64 -tc
        > 5m12.972s pfgw64 scriptify
        > 4m4.811s gmp (-O3/no pgo)
        > 4m9.148 pari-gp
        > 1m15s theoretical Woltman implementation
        > }
        >

        I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings
        {
        17.505s pfgw (3-prp)
        1m1.986s pfgw -tp
        1m13.789s gmp (-O3/no pgo)
        }

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