ECM Factoring for beginners
I was wondering if their are any basic papers/thesis on the internet on how ECM actually works.
thanks, brandon 
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 [url]http://www.mersennewiki.org/index.php/Elliptic_Curve_Method[/url] page. A mustread for anyone who wants to implement ECM is Peter Montgomery's thesis, "An FFT extension of the Elliptic Curve Method of Factorization" ([url]ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz[/url]). Alex 
[QUOTE=akruppa;91414]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 [url]http://www.mersennewiki.org/index.php/Elliptic_Curve_Method[/url] page. A mustread for anyone who wants to implement ECM is Peter Montgomery's thesis, "An FFT extension of the Elliptic Curve Method of Factorization" ([url]ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz[/url]). Alex[/QUOTE] There is also Peter's "Speeding the Pollard and Elliptic Curve Methods of Factorization" back in Math. Comp. in the '87 Lehmer issue. 
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 
[QUOTE=akruppa;91493]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[/QUOTE] Newcomer to factoring or newcomer to math beyond the high school level? The latter will have great difficulty with either paper. 
In order to program [URL="http://www.alpertron.com.ar/ECM.HTM"]my ECM factoring applet[/URL] I used Richard Brent's publication [URL="http://wwwmaths.anu.edu.au/~brent/pd/rpb161.pdf"]Factorization of the tenth Fermat Number[/URL] and Peter Montogomery's thesis cited above, among other online resources.

All times are UTC. The time now is 02:01. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.