20071024, 14:05  #1 
Oct 2007
7_{16} Posts 
Elliptic curve method
I'm a student of engeneering and i have to do a program using GMP pakage that factorize big_int number with Lenstra algorithm!!I want know if somebody has documentation about lenstra second stage, is an optimization of the original algorithm..thanks to all!!!

20071024, 14:39  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
A very good explanation of a fast stage 2 for ECM is in P.L. Montgomery's thesis, available at ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz. It is a Gzipcompressed Postscript file.
I'm one of the developers of GMPECM, if you would like to discuss details of stage 2 implementations for ECM, feel free to email me at kruppa@in.tum.de Alex Last fiddled with by akruppa on 20071024 at 14:40 
20071024, 15:14  #3  
Oct 2007
7 Posts 
Quote:
Thank u very much i've implemented the algorithm, i will send u the program when i will finish so i can explain what you think!!!if you want.... 

20071024, 21:15  #4 
"Jason Goatcher"
Mar 2005
3·7·167 Posts 

20071025, 20:39  #5 
Oct 2007
7 Posts 
i implement Lenstra algorithm and i want know if is a good result it's factorize a number of 53 digits in 41 seconds!?for you is a good result?

20071025, 20:45  #6 
Oct 2007
7 Posts 
My implementation found a prime factor of n that is 20 digits!!it seems good or no?

20071025, 22:40  #7  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Quote:
For an all new implementation by a new student of factoring with elliptic curves, it's very promising though! Alex Last fiddled with by akruppa on 20071025 at 22:40 

20071026, 12:17  #8 
Oct 2007
7 Posts 
Thank you very much!!

20071101, 11:22  #9 
Oct 2007
7_{8} Posts 
I want know if implementing tryal division and pollard rho before ECM can do a significant improvements for the performs????

20071101, 11:59  #10 
(loop (#_fork))
Feb 2006
Cambridge, England
1934_{16} Posts 
I don't think so; the only improvement would be that you would be working on a slightly smaller number, and the first few cycles of ECM would remove any factor that trial division or pollardrho could find.

20071101, 13:03  #11 
"Nancy"
Aug 2002
Alexandria
9A3_{16} Posts 
For numbers that contain very small prime factors it can be hard to get prime factorizations with only ECM. It tends to find composite factors in this case. Trial division by primes up to 1 million or so is so easy to write and so quick to execute that it's worthwhile, imo.
Alex 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Elliptic curve arithmetic  burrobert  GMPECM  6  20121108 13:05 
Ellipticcurve Lfunction question  fivemack  Math  0  20100822 14:52 
Elliptic Curve Arithmetic  Raman  Math  8  20090413 19:20 
Elliptic Curve Method factoring  Fermat numbers  philmoore  Math  131  20061218 06:27 
Elliptic Curve Method  the theory  philmoore  Math  2  20021112 01:11 