gmp-ecm questions

[yoyo]

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

[akruppa]

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

[Batalov]

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>

[Andi47]

Originally Posted by Batalov

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?

[jasonp]

Originally Posted by akruppa

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.

[yoyo]

Originally Posted by jasonp

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

[fivemack]

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.

[10metreh]

Originally Posted by yoyo

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

[jasonp]

Originally Posted by yoyo

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.

[yoyo]

Originally Posted by jasonp

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

[jasonp]

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.