ECM Factoring for beginners

[BWetter246]

I was wondering if their are any basic papers/thesis on the internet on how ECM actually works.

thanks,
brandon

[akruppa]

Depends on how deeply you want to understand how it works... could be anything between why sometimes factors pop out any why large B1,B2 values have a higher chance of finding a given factor, to details of elliptic curve arithmetic and curve parameterisation.

A starting point is the http://www.mersennewiki.org/index.ph...c_Curve_Method page. A must-read for anyone who wants to implement ECM is Peter Montgomery's thesis, "An FFT extension of the Elliptic Curve Method of Factorization" (ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz).

Alex

[R.D. Silverman]

Originally Posted by akruppa

Depends on how deeply you want to understand how it works... could be anything between why sometimes factors pop out any why large B1,B2 values have a higher chance of finding a given factor, to details of elliptic curve arithmetic and curve parameterisation.

A starting point is the http://www.mersennewiki.org/index.ph...c_Curve_Method page. A must-read for anyone who wants to implement ECM is Peter Montgomery's thesis, "An FFT extension of the Elliptic Curve Method of Factorization" (ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz).

Alex

There is also Peter's "Speeding the Pollard and Elliptic Curve Methods of
Factorization" back in Math. Comp. in the '87 Lehmer issue.

[akruppa]

Indeed there is, and without doubt it is a landmark work on the subject. But the style of that paper is very terse and it may not be the best text to read for a newcomer. His thesis spends a little more time on explaining the various ideas so I think it's better for a first read.

Alex

[R.D. Silverman]

Originally Posted by akruppa

Indeed there is, and without doubt it is a landmark work on the subject. But the style of that paper is very terse and it may not be the best text to read for a newcomer. His thesis spends a little more time on explaining the various ideas so I think it's better for a first read.

Alex

Newcomer to factoring or newcomer to math beyond the high school level?
The latter will have great difficulty with either paper.

[alpertron]

In order to program my ECM factoring applet I used Richard Brent's publication Factorization of the tenth Fermat Number and Peter Montogomery's thesis cited above, among other online resources.