Re: [PrimeNumbers] ECM + Montgomery modmul?
- --- D�cio Luiz Gazzoni Filho <decio@...> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----Not wasting time at all. I didn;t know the capabilities of Miracl in this
> 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.
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.
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