Elliptic curve method

[Dirac]

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!!!

[akruppa]

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 Gzip-compressed Postscript file.

I'm one of the developers of GMP-ECM, if you would like to discuss details of stage 2 implementations for ECM, feel free to email me at kruppa@in.tum.de

Alex

[Dirac]

Originally Posted by akruppa

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 Gzip-compressed Postscript file.

I'm one of the developers of GMP-ECM, if you would like to discuss details of stage 2 implementations for ECM, feel free to email me at kruppa@in.tum.de

Alex

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

[jasong]

Originally Posted by Dirac

i will send u the program when i will finish so i can explain what you think!!!

I know it's simply a language problem, but that sentence cracks me up!!!

[Dirac]

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?

[Dirac]

My implementation found a prime factor of n that is 20 digits!!it seems good or no?

[akruppa]

Originally Posted by Dirac

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?

Depends entirely on what the size of the smallest prime factor is.

Originally Posted by Dirac

My implementation found a prime factor of n that is 20 digits!!it seems good or no?

It's a long, long way from a record... the current record is 67 digits, found by Bruce Dodson. See http://www.loria.fr/~zimmerma/records/ecmnet.html
For an all new implementation by a new student of factoring with elliptic curves, it's very promising though!

Alex

[Dirac]

Thank you very much!!

[Dirac]

I want know if implementing tryal division and pollard rho before ECM can do a significant improvements for the performs????

[fivemack]

Originally Posted by Dirac

I want know if implementing tryal division and pollard rho before ECM can do a significant improvements for the performs????

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 pollard-rho could find.

[akruppa]

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