mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   What size numbers are you testing with ECM? (https://www.mersenneforum.org/showthread.php?t=25115)

SethTro 2020-01-16 00:17

What size numbers are you testing with ECM?
 
I'm curious about what digit ranges the most ECM gets performed at.

gmp-ecm supports GPU stage 1 which is 10-50x faster for numbers up to 308 digits.
Is there benefit to increasing this limit to 616 digits?
Is there more benefit to speeding up the < 150 digit case?
the < 75 digit case?

VBCurtis 2020-01-16 01:07

For me, the most numbers are in 100-150 digit range for Aliquot sequence work, but the most time is in SNFS candidates in 200-300 digit range; I voted based on time spent.

I don't use GPU-ECM because my old Quadro cards crashed when I tried. I've never quite paid close enough attention to which linux/CUDA drivers work with Gpu-enhanced GMP-ECM, sigh.

R.D. Silverman 2020-01-16 01:13

[QUOTE=SethTro;535180]I'm curious about what digit ranges the most ECM gets performed at.
[/QUOTE]

Interesting question. I [i]guess[/i] [based on what is publicly reported] that it is
under 1024 bits.

[QUOTE]

gmp-ecm supports GPU stage 1 which is 10-50x faster for numbers up to 308 digits.

[/QUOTE]

One still must run stage 2. Even if GPU stage 1 took zero time the net result
only cuts the total time in half after running stage 2.

[QUOTE] { I numbered these]

(1) Is there benefit to increasing this limit to 616 digits?
(2) Is there more benefit to speeding up the < 150 digit case?
(3) the < 75 digit case?[/QUOTE]

(1) Benefit to whom? Certainly there is a benefit to those running ECM on composites
over 1024 bits. I can't even guess as to what fraction of total ECM time is spent on
such numbers.

(2) I would think the benefit would be marginal because such numbers readily yield
to NFS/QS.

(3) No! Such numbers are easy (almost trivial) with QS,

"benefit" is sufficiently fuzzy that I doubt there is a real answer.

SethTro 2020-01-16 01:42

[QUOTE=R.D. Silverman;535184]
One still must run stage 2. Even if GPU stage 1 took zero time the net result
only cuts the total time in half after running stage 2.
[/QUOTE]

You would also re-adjust your stage 2 bound. In the absurd case (stage 1 is instant) you would no longer run stage 2. If stage 1 could be run 10x faster, I suspect the overall process would be ~3x faster (from running a larger number of curves with B2=20xB1).

Maybe it's worth some work to compile B1,B2 values that take the same amount of time (I recall this is what your paper proves is ~optimal) on GPU stage 1, CPU stage 2 at different input sizes.

R.D. Silverman 2020-01-16 01:50

[QUOTE=SethTro;535187]You would also re-adjust your stage 2 bound. In the absurd case (stage 1 is instant) you would no longer run stage 2. If stage 1 could be run 10x faster, I suspect the overall process would be ~3x faster (from running a larger number of curves with B2=20xB1).

Maybe it's worth some work to compile B1,B2 values that take the same amount of time (I recall this is what your paper proves is ~optimal) on GPU stage 1, CPU stage 2 at different input sizes.[/QUOTE]

Finding a factor greater than 50 digits is almost unheard of without step 2.

One can find factors up to about 30 digits in step 1, but it is still somewhat rare (based on
my experience). I do find factors under 20 digits in step 1 fairly frequently. [but I do
not keep any data].

chris2be8 2020-01-16 16:59

I'm currently tuning my scripts to do ECM on my newest system. It has a fairly fast CPU, AMD Ryzen 5 2600 Six-Core Processor (with 12 hyperthreads), and a relatively slow GPU, GeForce GTX 760. The GPU does stage 1 about as fast as 5 hyperthreads on the CPU. So a speed up would be useful.

Most of the numbers I'm doing ECM on are 159-200 digits. But I'm doing enough 76-159 digit numbers that a speed up would be nice.

I've never done any ECM over 309 digits.

Below 75 digits a GPU is nearly useless, you need to do less than 100 curves of any given length and a GPU does several times as many per batch.

Does configuring ecm-gpu to do 512 bit arithmetic work correctly? My notes from last time this was discussed said it didn't always find factors it should.

Of course being able to do QS (or even better lattice sieving) on a GPU would be *very* nice.

Chris

SethTro 2020-01-16 19:05

[QUOTE=chris2be8;535239]
Does configuring ecm-gpu to do 512 bit arithmetic work correctly? My notes from last time this was discussed said it didn't always find factors it should.
[/QUOTE]

Can you point me at this discussion?
There are tests that pass so I would be slightly surprised but it's easy to imagine that something is depending on the symmetry of 2^6 in both places.

VBCurtis 2020-01-17 00:38

Start around post 160 of the GPU-ECM thread:

[url]https://mersenneforum.org/showthread.php?t=16480&page=4[/url]

SethTro 2020-01-17 02:01

[QUOTE=VBCurtis;535280]Start around post 160 of the GPU-ECM thread:

[url]https://mersenneforum.org/showthread.php?t=16480&page=4[/url][/QUOTE]

I see a little bit of discussion but nothing concrete.

I'll work on creating a test set of N + sigma that result in factors so I can test with 512, 1024, and 2048 bits.

Before I go and duplicate a lot of work is there a script / website that given a factor will tell me the min B1/B2 for a specific sigma that will find that factor? I can find this via binary search without too much cost (I only need precision in the thousands) but it feels like it might be easy to determine in PARI.

SethTro 2020-01-17 04:47

"Faking factors with Complex Multiplication"
[url]https://www.mersenneforum.org/showthread.php?t=6734[/url]

This ecm thread
[url]https://lists.gforge.inria.fr/pipermail/ecm-discuss/2005-September/003780.html[/url]

[url]https://homepages.cwi.nl/~herman/Zimmermann.pdf[/url]

have proven interesting. I think for the size factors (10-20 digits) that I want to fake, so that I can test they are correctly discovered, this should be fairly easy.

SethTro 2020-01-17 08:31

I'm up way to late but I got it coded up.

[CODE]
def GroupOrderParam3(p, sigma):
K = GF(p)
inv2_32 = inverse_mod(2 ** 32, p)
s = K(sigma * inv2_32)
A = K(4 * s - 2);
b = K(16* s + 2);
return factor(EllipticCurve([0,b*A,0,b^2,0]).order())

def smallGroupOrders(p, B1, B2, count):
inv2_32 = inverse_mod(2 ** 32, p)

for sigma in range(1000, 1000 + count):
f = GroupOrderParam3(p, sigma)
if len(f) <= 1:
print "What:", p, f
elif f[-2][0] <= B1 and f[-1][0] <= B2:
print "\t\t", sigma, f

import random
for p_digits in range(17, 25):
print (p_digits)
for i in range(10):
r = ZZ(random.randint(10 ** (p_digits-1), 10 ** p_digits))
p = Primes().next(r)
print "\t", i, p
smallGroupOrders(p, 1e3, 1e5, 832)

[/CODE]

[CODE]
...
9 127103063423215939
1401 2^8 * 3 * 5 * 17 * 41 * 149 * 157 * 641 * 3167
1478 2^5 * 13 * 19 * 421 * 587 * 947 * 68713
1527 2^8 * 5 * 7 * 17 * 113 * 157 * 571 * 82373
1706 2^5 * 3^2 * 17 * 29 * 101 * 617 * 937 * 15331
...
[/CODE]

Then testing ecm -gpu

[CODE]
eights:~/Projects/gmp-ecm-svn-official/trunk$ echo "127103063423215939*(3*10^29+7)^2" | ./ecm -gpu -sigma 3:1000 1e3 1e5
GMP-ECM 7.0.5-dev [configured with GMP 6.1.99, --enable-asm-redc, --enable-gpu, --enable-assert] [ECM]
Input number is 127103063423215939*(3*10^29+7)^2 (77 digits)
Using B1=1000, B2=108126, sigma=3:1000-3:1831 (832 curves)
GPU: Block: 32x32x1 Grid: 26x1x1 (832 parallel curves)
Computing 832 Step 1 took 23ms of CPU time / 291ms of GPU time
GPU: factor 127103063423215939 found in Step 2 with curve 401 (-sigma 3:1401)
GPU: factor 127103063423215939 found in Step 2 with curve 478 (-sigma 3:1478)
GPU: factor 127103063423215939 found in Step 2 with curve 527 (-sigma 3:1527)
GPU: factor 127103063423215939 found in Step 2 with curve 706 (-sigma 3:1706)
Computing 832 Step 2 on CPU took 1996ms
********** Factor found in step 2: 127103063423215939
Found prime factor of 18 digits: 127103063423215939
Composite cofactor (127103063423215939*(3*10^29+7)^2)/127103063423215939 has 59 digits
[/CODE]

But this does not always happen; sometimes I get more factors and sometimes less than expected.
Some of the missed factors appear to have group order that are B1 smooth but with higher powers
Not sure why I'd get extra. I'll do a full analysis soon


All times are UTC. The time now is 20:04.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.