mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2006-11-14, 01:52   #1
BWetter246
 
Aug 2005

100012 Posts
Default ECM Factoring for beginners

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

thanks,
brandon
BWetter246 is offline   Reply With Quote
Old 2006-11-14, 03:05   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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

Last fiddled with by akruppa on 2006-11-14 at 03:05
akruppa is offline   Reply With Quote
Old 2006-11-14, 14:17   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-11-14, 18:18   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2006-11-14, 18:37   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-11-15, 13:19   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22×3×113 Posts
Default

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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Block Wiedemann for beginners paul0 Factoring 7 2015-11-16 17:09
ECM program for beginners. literka GMP-ECM 0 2012-04-29 23:54
RAID for beginners xilman Lounge 2 2009-08-17 17:32
LMH for Beginners on V5 Bundu Lone Mersenne Hunters 3 2008-12-30 17:41
A beginners question about ECM roger GMP-ECM 3 2006-11-29 22:36

All times are UTC. The time now is 03:46.

Fri May 14 03:46:00 UTC 2021 up 35 days, 22:26, 0 users, load averages: 2.31, 2.74, 2.90

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.