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

Re: [PrimeNumbers] ECM + Montgomery modmul?

Expand Messages
  • Phil Carmody
    ... Not wasting time at all. I didn;t know the capabilities of Miracl in this regard, so that little voyage of discovery was for my benefit as well as others.
    Message 1 of 5 , Oct 30, 2002
    • 0 Attachment
      --- D�cio Luiz Gazzoni Filho <decio@...> wrote:
      > -----BEGIN PGP SIGNED MESSAGE-----
      > Hash: SHA1
      >
      > > Are you sure that;s not how it's done already?
      > >
      > >
      > > Looking at the Miracl lenstra.cpp source, there's:
      > ...
      > > So Mike Scott has at least implemented it that way already.
      > >
      > > Phew!
      > >
      > > I'm fairly sure that the use of Montgomery form was suggested by Montgomery
      > > himself in his 1987 paper "Speeding the Pollard and Elliptic Curve
      > > Methods". Maybe Paul L. could confirm this, as he seems more intimate wiht
      > > the history of ECM?
      > >
      > > Phil
      >
      > My only resource on ECM is ``Prime Numbers: A Computational Perspective'' by
      > R. Crandall and C. Pomerance. The book covers Montgomery multiplication,
      > though not addition, on Chapter 9 (efficient implementation techniques).
      > Nowhere was it suggested on Chapter 7 (on elliptic curves) the use of
      > Montgomery modmul for implementation. I also glanced over P. Montgomery's PhD
      > dissertation and found no mention of it.
      >
      > Sorry for wasting your time.

      Not wasting time at all. I didn;t know the capabilities of Miracl in this
      regard, so that little voyage of discovery was for my benefit as well as
      others. I had _hoped_ it was being used, but the best way to find out is to
      check the details where it's most obvious - in the source.

      If you've not come across 'Miracl' before, then it's a freely available
      library for bignum and other number-theoretical operations.
      The home page from which you can get miracl is http://indigo.ie/

      It's a _very_ competant library, and comes with loads of example code,
      including a whole host of factoring algorithms. I personally know of about a
      dozen people who as a first resort when given a factoring problem will run
      the Miracl example program! I'm one myself, for example.

      It's a shame that C&P's PNaCP didn't list that particular implementation
      detail, but I guess that's because of the order in which the book is laid
      out. Having said that there are a couple of times when things are used before
      they're formally introduced.

      Phil


      =====
      First rule of Factor Club - you do not talk about Factor Club.
      Second rule of Factor Club - you DO NOT talk about Factor Club.
      Third rule of Factor Club - when the cofactor is prime, or you've trial-
      divided up to the square root of the number, the factoring is over.

      __________________________________________________
      Do you Yahoo!?
      HotJobs - Search new jobs daily now
      http://hotjobs.yahoo.com/
    Your message has been successfully submitted and would be delivered to recipients shortly.