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

Re: Lucas tests with Fermat tests for free

Expand Messages
  • djbroadhurst
    ... Indeed. The decoupled version of CP Algorithm 3.5.9, with Paul s preferred parameters, is Lucas with parameters (P,Q) = (c,1); Fermat with base d = 2*x+5,
    Message 1 of 33 , May 30, 2012
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      Phil Carmody <thefatphil@...> wrote:

      > One caveat with two-for-the-price-of-one deals is that the
      > two bits you get back might not actually be independent of
      > each other, so you'd not be getting full value for money.
      > It applies to all the Grantham one too of course.

      Indeed. The decoupled version of CP Algorithm 3.5.9,
      with Paul's preferred parameters, is
      Lucas with parameters (P,Q) = (c,1);
      Fermat with base d = 2*x+5, where x is the smallest
      non-negative integer for which kronecker(x^2-4,N) = -1.
      These are not chosen independently by Paul, since

      c = (d^2 - 2*d + 9)/(4*d) mod N ... [1]

      turns out to be the rather delicate condition for
      Paul's "Lucas test with Fermat test for free".

      It is hard to see why [1] might induce a
      correlation between the probabilities for Lucas
      pseudoprimality and Fermat pseudoprimality.
      But Phil is correct in pointing out that we
      cannot entirely discount that possibility.

      When kronecker(5,N) = -1, Grantham suggests
      using a Frobenius test for which the CP separation
      gives c = 3, for Lucas, and d = 5, for Fermat,
      while BPSW choose c = 3 and d = 2. We likewise
      cannot discount the possibility of correlated
      probabilities in such circumstance.

      David
    • 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
      • 0 Attachment
        --- 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.