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

Re: [PrimeNumbers] Lucas tests with Fermat tests for free

Expand Messages
  • Phil Carmody
    ... Sounds pretty neat. 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
    Message 1 of 33 , May 30 12:33 AM
    • 0 Attachment
      --- On Wed, 5/30/12, djbroadhurst <d.broadhurst@...> wrote:
      > "paulunderwooduk" <paulunderwood@> wrote:
      >
      > > Please see my draft paper
      >
      > http://www.mersenneforum.org/showpost.php?p=298027&postcount=44

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

      Sounds pretty neat. 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.

      Note that generally mathematicians and computer scientists prefer their Big-Oh costs to refer to the size of the input, not the value of the input. So the cost of the FFT is O(d^(1+eps)), where d=lg(n), rather than O(n^(1+eps)).

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