mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

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

Reply
 
Thread Tools
Old 2020-01-16, 00:17   #1
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

2×191 Posts
Default 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?
SethTro is offline   Reply With Quote
Old 2020-01-16, 01:07   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

13C916 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2020-01-16, 01:13   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by SethTro View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2020-01-16, 01:42   #4
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

2·191 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
SethTro is offline   Reply With Quote
Old 2020-01-16, 01:50   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by SethTro View Post
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].
R.D. Silverman is offline   Reply With Quote
Old 2020-01-16, 16:59   #6
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22·32·61 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2020-01-16, 19:05   #7
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

1011111102 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
SethTro is offline   Reply With Quote
Old 2020-01-17, 00:38   #8
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5×1,013 Posts
Default

Start around post 160 of the GPU-ECM thread:

https://mersenneforum.org/showthread.php?t=16480&page=4
VBCurtis is offline   Reply With Quote
Old 2020-01-17, 02:01   #9
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

2·191 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
SethTro is offline   Reply With Quote
Old 2020-01-17, 04:47   #10
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

38210 Posts
Default

"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
SethTro is offline   Reply With Quote
Old 2020-01-17, 08:31   #11
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

2×191 Posts
Default

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
SethTro is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What size numbers can CudaLucas handle? robertfrost GPU Computing 8 2019-01-10 13:14
Why have ECM testing for known non-prime Mersenne numbers? sd235 Information & Answers 12 2018-12-06 17:56
Testing my numbers Vicodin Information & Answers 21 2017-05-02 05:11
About GNFS and size of smooth numbers JuanraG Factoring 7 2014-11-04 16:43
testing big numbers sagan_fan Math 8 2002-10-09 21:20

All times are UTC. The time now is 01:51.


Sun Nov 28 01:51:59 UTC 2021 up 127 days, 20:20, 0 users, load averages: 1.66, 1.50, 1.35

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.