mersenneforum.org (https://www.mersenneforum.org/index.php)
-   GMP-ECM (https://www.mersenneforum.org/forumdisplay.php?f=55)
-   -   ECM Factoring for beginners (https://www.mersenneforum.org/showthread.php?t=6607)

 BWetter246 2006-11-14 01:52

ECM Factoring for beginners

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

thanks,
brandon

 akruppa 2006-11-14 03:05

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 must-read 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

 R.D. Silverman 2006-11-14 14:17

[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 must-read 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.

 akruppa 2006-11-14 18:18

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 2006-11-14 18:37

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

 alpertron 2006-11-15 13:19

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.