mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-10-24, 14:05   #1
Dirac
 
Oct 2007

7 Posts
Default 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!!!
Dirac is offline   Reply With Quote
Old 2007-10-24, 14:39   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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

Last fiddled with by akruppa on 2007-10-24 at 14:40
akruppa is offline   Reply With Quote
Old 2007-10-24, 15:14   #3
Dirac
 
Oct 2007

7 Posts
Default

Quote:
Originally Posted by akruppa View Post
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....
Dirac is offline   Reply With Quote
Old 2007-10-24, 21:15   #4
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

350710 Posts
Default

Quote:
Originally Posted by Dirac View Post
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!!!
jasong is offline   Reply With Quote
Old 2007-10-25, 20:39   #5
Dirac
 
Oct 2007

7 Posts
Default

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 is offline   Reply With Quote
Old 2007-10-25, 20:45   #6
Dirac
 
Oct 2007

7 Posts
Default

My implementation found a prime factor of n that is 20 digits!!it seems good or no?
Dirac is offline   Reply With Quote
Old 2007-10-25, 22:40   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by Dirac View Post
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.

Quote:
Originally Posted by Dirac View Post
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

Last fiddled with by akruppa on 2007-10-25 at 22:40
akruppa is offline   Reply With Quote
Old 2007-10-26, 12:17   #8
Dirac
 
Oct 2007

7 Posts
Default

Thank you very much!!
Dirac is offline   Reply With Quote
Old 2007-11-01, 11:22   #9
Dirac
 
Oct 2007

78 Posts
Default

I want know if implementing tryal division and pollard rho before ECM can do a significant improvements for the performs????
Dirac is offline   Reply With Quote
Old 2007-11-01, 11:59   #10
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

638310 Posts
Default

Quote:
Originally Posted by Dirac View Post
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.
fivemack is offline   Reply With Quote
Old 2007-11-01, 13:03   #11
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Elliptic curve arithmetic burrobert GMP-ECM 6 2012-11-08 13:05
Elliptic-curve L-function question fivemack Math 0 2010-08-22 14:52
Elliptic Curve Arithmetic Raman Math 8 2009-04-13 19:20
Elliptic Curve Method factoring - Fermat numbers philmoore Math 131 2006-12-18 06:27
Elliptic Curve Method - the theory philmoore Math 2 2002-11-12 01:11

All times are UTC. The time now is 17:28.

Tue Apr 13 17:28:59 UTC 2021 up 5 days, 12:09, 1 user, load averages: 4.51, 4.84, 4.64

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.