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

Thread Tools 
20200116, 00:17  #1 
"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.
gmpecm supports GPU stage 1 which is 1050x 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 20200116 at 00:19 Reason: removed poll options from post details? 
20200116, 01:07  #2 
"Curtis"
Feb 2005
Riverside, CA
3·19·89 Posts 
For me, the most numbers are in 100150 digit range for Aliquot sequence work, but the most time is in SNFS candidates in 200300 digit range; I voted based on time spent.
I don't use GPUECM because my old Quadro cards crashed when I tried. I've never quite paid close enough attention to which linux/CUDA drivers work with Gpuenhanced GMPECM, sigh. 
20200116, 01:13  #3  
Nov 2003
1110100100100_{2} Posts 
Quote:
under 1024 bits. Quote:
only cuts the total time in half after running stage 2. Quote:
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. 

20200116, 01:42  #4  
"Seth"
Apr 2019
389 Posts 
Quote:
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. 

20200116, 01:50  #5  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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]. 

20200116, 16:59  #6 
Sep 2009
2^{3}·5^{2}·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 SixCore 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 159200 digits. But I'm doing enough 76159 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 ecmgpu 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 
20200116, 19:05  #7  
"Seth"
Apr 2019
110000101_{2} Posts 
Quote:
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. 

20200117, 00:38  #8 
"Curtis"
Feb 2005
Riverside, CA
3×19×89 Posts 
Start around post 160 of the GPUECM thread:
https://mersenneforum.org/showthread.php?t=16480&page=4 
20200117, 02:01  #9  
"Seth"
Apr 2019
605_{8} Posts 
Quote:
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. 

20200117, 04:47  #10 
"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 (1020 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 20200117 at 04:55 
20200117, 08:31  #11 
"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_digits1), 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 ... Code:
eights:~/Projects/gmpecmsvnofficial/trunk$ echo "127103063423215939*(3*10^29+7)^2"  ./ecm gpu sigma 3:1000 1e3 1e5 GMPECM 7.0.5dev [configured with GMP 6.1.99, enableasmredc, enablegpu, enableassert] [ECM] Input number is 127103063423215939*(3*10^29+7)^2 (77 digits) Using B1=1000, B2=108126, sigma=3:10003: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 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 20200117 at 08:36 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What size numbers can CudaLucas handle?  robertfrost  GPU Computing  8  20190110 13:14 
Why have ECM testing for known nonprime Mersenne numbers?  sd235  Information & Answers  12  20181206 17:56 
Testing my numbers  Vicodin  Information & Answers  21  20170502 05:11 
About GNFS and size of smooth numbers  JuanraG  Factoring  7  20141104 16:43 
testing big numbers  sagan_fan  Math  8  20021009 21:20 