mersenneforum.org  

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

Reply
 
Thread Tools
Old 2008-12-08, 21:57   #1
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

5×112 Posts
Default gmp-ecm questions

Hello,
I have some questions regarding gmp-ecm. I downloaded it and compiled it on my Linux32 box according to the description.

1) Can somebody post an input number and a B1 which runs for some minutes (e.g. 30min) and than finds a factor?

2) What is the best way to compile it for the best performance, but it should run on any Linux32 system?

3) How about runtime? I expect, that runtime depends on input number and B1. I will use only "ecm [B1] < in.txt". But how is the relation, double B1 -> double runtime? Any indication is very welcome.

4) If a factor with ecm is found, is there a way to verify it?

yoyo
yoyo is offline   Reply With Quote
Old 2008-12-08, 23:47   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

1) Whether a factor is found or not depends not only on the B1 value, but also on the sigma value of the curve. One run that finds a factor is, for example

echo "(2^2048+1)/974849/319489" | ecm -sigma 2929833171 50000

It takes only a few seconds.


2) Speed depends greatly on how GMP was compiled. If you need the same binary to run on all x86 cpus, you could try a "fat" GMP binary that includes code for different cpus and decides at run-time which code to use for the cpu it's running on. I've never tried building fat GMP binaries, though, so I can't give much advice here.


3) Run time is roughly linear in B1, yes. There's some overhead, but usually it's small compared to the actual curve arithmetic, and time for the latter grows very nearly like B1 (in stage 1 anyway, but stage 2 tries to choose parameters so that it takes no more time than stage 1 so total time still grows roughly linearly)


4) What do you mean? Verify that it divides the input number? If you're on a Unix-like system, you could use "bc" to compute the remainder. Or do you mean: test whether the factor (and/or cofactor) found is a prime? For numbers that are not too large, you could try stuff like Pari/GP (http://pari.math.u-bordeaux.fr/) which has a primality proving available in
the isprime() function.

Alex

Last fiddled with by akruppa on 2008-12-11 at 14:47 Reason: typo
akruppa is offline   Reply With Quote
Old 2008-12-09, 00:07   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·32·7·37 Posts
Default GMP 4.3.0 benchmarks are shocking

I wonder how fast GMP-ECM will run with the 4.3.0.
The release schedule mentions late 2008 or early 2009.
Is there anyone from the inner circles of GMP, who knows more precisely?

Anyway, soon we will find out.

<S>
Batalov is offline   Reply With Quote
Old 2008-12-09, 10:26   #4
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2·17·73 Posts
Default

Quote:
Originally Posted by Batalov View Post
I wonder how fast GMP-ECM will run with the 4.3.0.
The release schedule mentions late 2008 or early 2009.
Is there anyone from the inner circles of GMP, who knows more precisely?

Anyway, soon we will find out.

<S>
Looks like a nice speedup, if I understand the numbers correctly!

BTW: I just recognized that I am still running 4.2.2 - is there a speedup between 4.2.2 and 4.2.4 for GMP-ECM?
Andi47 is offline   Reply With Quote
Old 2008-12-09, 15:59   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

Quote:
Originally Posted by akruppa View Post
2) Speed depends greatly on how GMP was compiled. If you need the same binary to run on all x86 cpus, you could try a "fat" GMP binary that includes code for different cpus and decides at run-time which code to use for the cpu it's running on. I've never tried building fat GMP binaries, though, so I can't give much advice here.
A fat version of GMP is no trouble at all to compile, and works transparently. I know you've also discussed a fat version of GMP-ECM, that would be nice too and would hopefully make unnecessary all those arch-specific compiles that people seem to need. Maybe I can help in that regard.
jasonp is offline   Reply With Quote
Old 2008-12-09, 18:02   #6
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

5·112 Posts
Default

Quote:
Originally Posted by jasonp View Post
A fat version of GMP is no trouble at all to compile, and works transparently. I know you've also discussed a fat version of GMP-ECM, that would be nice too and would hopefully make unnecessary all those arch-specific compiles that people seem to need. Maybe I can help in that regard.
Would be really nice to have such fat binary which selects the best core at start time. This is what I need, one binary which runs on all (amd/intel) 32 bit Linux systems and selects the best core.
Later I need the same for Linux64, and Win 32/64.

Has somebody thought about to port GMP-ECM to cuda and PS3 (with full usage of SPE'S)?
yoyo
yoyo is offline   Reply With Quote
Old 2008-12-09, 18:24   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·3,191 Posts
Default

People have thought about running ECM on graphics cards and on PS3; indeed, I have a suspicion that some of the ECM records at EPFL were set on their PS3 cluster.

http://cado.gforge.inria.fr/workshop/slides/bos.pdf and http://cado.gforge.inria.fr/workshop/slides/lange.pdf will probably interest you.

(linked from http://cado.gforge.inria.fr/workshop/abstracts.html)

The graphics-card implementation is stage 1 only, and about the same speed on a GTX280 as all four processors of a Q6600.

Last fiddled with by fivemack on 2008-12-09 at 18:28
fivemack is online now   Reply With Quote
Old 2008-12-09, 18:30   #8
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by yoyo View Post
1) Can somebody post an input number and a B1 which runs for some minutes (e.g. 30min) and than finds a factor?
807850509515205600330843021648479350477160574403074679908428000906800467880030894881223183
appeared in my aliquot sequence (www.mersenneforum.org/showthread.php?t=11007, this may interest you). Run curves on this number (401 is normal, run more if you don't find factors) with B1 = 25e4. The factors should be:

423261437229815320090393538611 * 1908632439568485010120359575805448825018466413856309794908853

Last fiddled with by 10metreh on 2008-12-09 at 18:34
10metreh is offline   Reply With Quote
Old 2008-12-09, 20:28   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

Quote:
Originally Posted by yoyo View Post
Would be really nice to have such fat binary which selects the best core at start time. This is what I need, one binary which runs on all (amd/intel) 32 bit Linux systems and selects the best core.
Later I need the same for Linux64, and Win 32/64.
Just configure GMP with --enable-fat and then compile. I doubt you can do that with the windows development tools though (Brian Gladman maintains those projects). GMP-ECM has some SSE2 code that is selected by the configure script, but it does no runtime configuration.
jasonp is offline   Reply With Quote
Old 2008-12-09, 21:11   #10
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

5·112 Posts
Default

Quote:
Originally Posted by jasonp View Post
Just configure GMP with --enable-fat and then compile. I doubt you can do that with the windows development tools though (Brian Gladman maintains those projects). GMP-ECM has some SSE2 code that is selected by the configure script, but it does no runtime configuration.
I configured and compiled it. Where did you found it? Is it somewhere documented this option?
yoyo
yoyo is offline   Reply With Quote
Old 2008-12-10, 00:05   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

Look for the documentation in the source package, in texinfo format. The file is gmp.info-1

As far as I know the option to build a fat binary is limited to 32-bit x86 only.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Two questions: Dubslow GPU Computing 1 2011-08-05 18:22
Questions about the QS Carmichael Factoring 8 2007-04-10 11:30
Questions OmbooHankvald Prime Sierpinski Project 2 2005-08-01 20:18
LLR questions OmbooHankvald Math 6 2005-06-23 11:42
A few questions :) xtreme2k Lounge 59 2002-10-31 06:20

All times are UTC. The time now is 18:22.

Wed Feb 24 18:22:13 UTC 2021 up 83 days, 14:33, 0 users, load averages: 1.63, 1.90, 1.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.