mersenneforum.org What size numbers are you testing with ECM?
 Register FAQ Search Today's Posts Mark Forums Read

 View Poll Results: What size numbers do you ECM the most? <100 digits 0 0% 100-149 digits 6 35.29% 150-199 digits 7 41.18% 200-299 digits 5 29.41% 300+ digits 5 29.41% Multiple Choice Poll. Voters: 17. You may not vote on this poll

 2020-01-16, 00:17 #1 SethTro     "Seth" Apr 2019 389 Posts 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? Last fiddled with by SethTro on 2020-01-16 at 00:19 Reason: removed poll options from post details?
 2020-01-16, 01:07 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 3·19·89 Posts 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.
2020-01-16, 01:13   #3
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by SethTro I'm curious about what digit ranges the most ECM gets performed at.
Interesting question. I guess [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.
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?
(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.

2020-01-16, 01:42   #4
SethTro

"Seth"
Apr 2019

389 Posts

Quote:
 Originally Posted by R.D. Silverman 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.
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.

2020-01-16, 01:50   #5
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by SethTro 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.
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].

 2020-01-16, 16:59 #6 chris2be8     Sep 2009 23·52·11 Posts 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
2020-01-16, 19:05   #7
SethTro

"Seth"
Apr 2019

1100001012 Posts

Quote:
 Originally Posted by chris2be8 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.
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.

 2020-01-17, 00:38 #8 VBCurtis     "Curtis" Feb 2005 Riverside, CA 3×19×89 Posts Start around post 160 of the GPU-ECM thread: https://mersenneforum.org/showthread.php?t=16480&page=4
2020-01-17, 02:01   #9
SethTro

"Seth"
Apr 2019

6058 Posts

Quote:
 Originally Posted by VBCurtis Start around post 160 of the GPU-ECM thread: https://mersenneforum.org/showthread.php?t=16480&page=4
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.

 2020-01-17, 04:47 #10 SethTro     "Seth" Apr 2019 389 Posts "Faking factors with Complex Multiplication" https://www.mersenneforum.org/showthread.php?t=6734 This ecm thread https://lists.gforge.inria.fr/piperm...er/003780.html https://homepages.cwi.nl/~herman/Zimmermann.pdf 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. Last fiddled with by SethTro on 2020-01-17 at 04:55
 2020-01-17, 08:31 #11 SethTro     "Seth" Apr 2019 389 Posts 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: ... 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 ... 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 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 Last fiddled with by SethTro on 2020-01-17 at 08:36

 Similar Threads Thread Thread Starter Forum Replies Last Post robertfrost GPU Computing 8 2019-01-10 13:14 sd235 Information & Answers 12 2018-12-06 17:56 Vicodin Information & Answers 21 2017-05-02 05:11 JuanraG Factoring 7 2014-11-04 16:43 sagan_fan Math 8 2002-10-09 21:20

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

Tue Dec 7 11:22:52 UTC 2021 up 137 days, 5:51, 0 users, load averages: 1.96, 1.69, 1.60