mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Hardware > GPU Computing

Reply
 
Thread Tools
Old 2019-10-12, 01:23   #1
mnd9
 
Jun 2019
Boston, MA

468 Posts
Default TF small exponents on GPU?

Is there any way to do TF work on very small (ie less than 10^5) exponents using GPUs? It seems that mfaktc and mfakto have lower limits for exponents unless there is some way to modify these—is there an alternative GPU program for this type of work?
mnd9 is offline   Reply With Quote
Old 2019-10-12, 01:44   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22·3·587 Posts
Default

If there is a way to do TF on small exponents I hope no one tells you.

TF on exponents below 10,000 is a complete waste of time. You will find zero factors -- guaranteed.

To find new factors you must do ECM. And then you'll need a lot of luck, but at least you won't be wasting your time and resources.
Prime95 is offline   Reply With Quote
Old 2019-10-12, 03:21   #3
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

Here is the ECM Report for exponents under 10,000.

Based on this, we know with a very high degree of certainty that there are no unknown factors smaller than 30 digits for exponents in this range, or about 100 bits.

And that's a very conservative estimate; actually, no factor smaller than 35 digits (116 bits) has been discovered for exponents in this range in the past eight years.

Trial factoring can't find such large factors, unless you spend way more than a trillion years on it.
GP2 is offline   Reply With Quote
Old 2019-10-12, 03:25   #4
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

Quote:
Originally Posted by Prime95 View Post
To find new factors you must do ECM. And then you'll need a lot of luck, but at least you won't be wasting your time and resources.
You probably will be wasting your time, because Ryan Propper is already working that range and finding large factors and he clearly has a ton of resources.
GP2 is offline   Reply With Quote
Old 2019-10-12, 03:58   #5
masser
 
masser's Avatar
 
Jul 2003
wear a mask

2·17·41 Posts
Default

Is there a way to perform ECM curves on a GPU?
masser is offline   Reply With Quote
Old 2019-10-12, 04:07   #6
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11011100001002 Posts
Default

Quote:
Originally Posted by GP2 View Post
You probably will be wasting your time, because Ryan Propper is already working that range and finding large factors and he clearly has a ton of resources.
Yes, Ryan clearly has a better chance of finding a new factor. It is like LL testing, curtisc has you outgunned, but you still have a chance. Just ask Patrick Laroche a winner on his fourth attempt :)

Quote:
Originally Posted by masser View Post
Is there a way to perform ECM curves on a GPU?
I think GMP-ECM can be compiled to run stage 1 on very small numbers, but I don't know any of the details.
Prime95 is offline   Reply With Quote
Old 2019-10-12, 05:35   #7
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

Quote:
Originally Posted by Prime95 View Post
I think GMP-ECM can be compiled to run stage 1 on very small numbers, but I don't know any of the details.
From the README.gpu file of GMP-ECM:

Quote:
The default implementation of the arithmetic for the GPU restricts
integers to be smaller than 2^1018. This restriction can be altered by
changing the source code but do so at your own risk because support
from the GMP-ECM team will be very limited.
Every exponent smaller than 1018 has already been fully factored. So in practice, no.
GP2 is offline   Reply With Quote
Old 2019-10-12, 08:26   #8
hansl
 
hansl's Avatar
 
Apr 2019

5×41 Posts
Default

Quote:
Originally Posted by GP2 View Post
Every exponent smaller than 1018 has already been fully factored. So in practice, no.
But there are some Mersenne numbers slightly larger than that, which have *some* known factors, such that after dividing their known factors, the leftover would be less than 1018 bits.

Quote:
Originally Posted by GP2 View Post
The bottom table on this page: "ECM on Mersenne numbers with known factors" would be a place to start.

So the first number: M1213 for example has a composite cofactor of 986 bits.
hansl is offline   Reply With Quote
Old 2019-10-12, 12:33   #9
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

2×3×227 Posts
Default

Quote:
Originally Posted by masser View Post
Is there a way to perform ECM curves on a GPU?
This is something I've hoped for a long time. One day, perhaps...
storm5510 is offline   Reply With Quote
Old 2019-10-12, 14:45   #10
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

Quote:
Originally Posted by hansl View Post
The bottom table on this page: "ECM on Mersenne numbers with known factors" would be a place to start.
Here is the list of not-fully-factored exponents below 1500. The ones that meet the criteria of the cofactor being 1018 bits (or nearly do) are indicated.

I used FactorDB for the cofactor size in digits, so the bit size is approximate and the actual value may be off by one or two or three.

Using https://www.mersenne.ca/manyfactors.php I made sure that there are no other candidates of any size with 5 factors or more. For any exponent above 1500 with only 4 factors or less, the factors would need to total at least 482 bits to make the list (i.e., be of size at least 120 bits on average), and that's the absolute best-case scenario. Highly unlikely.

Code:
1213	297 digits ≈ 987 bits
1217	248 digits ≈ 824 bits
1229	284 digits ≈ 944 bits
1231	329 digits
1237	303 digits ≈ 1007 bits
1249	326 digits
1259	309 digits ≈ 1027 bits
1283	347 digits
1291	348 digits
1297	302 digits ≈ 1004 bits
1319	307 digits = 1020 bits (exactly 1019.248)
1367	375 digits
1381	352 digits
1399	369 digits
1423	412 digits
1429	403 digits
1433	386 digits
1439	380 digits
1447	360 digits
1451	407 digits
1453	418 digits
1481	311 digits ≈ 1033 bits
1483	405 digits
1489	295 digits ≈ 979 bits

Last fiddled with by GP2 on 2019-10-12 at 14:56
GP2 is offline   Reply With Quote
Old 2019-10-13, 03:20   #11
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3×5×172 Posts
Default I suspect very slim odds.

In the past several months Ryan Propper found a first factor for about a dozen exponents under 9999.
None of the factor found results indicated how many curves were tried or at what B1/B2 levels. Nor were any unsuccessful attempts reported.
But I suggest that in order to find that many factors for so many small exponents he must have done a heck of a lot of curves.
Since they were not reported these curves must be redone in order to be recorded.
Further I hope to be proven wrong soon, but I tend to believe that since Ryan hasn't reported any Factors recently he has done all the ECM for these small exponents that he sees value in.
Maybe all the way to PrimeNets 30 or 40 or 50 + digits levels.
If he did his ECM in a way that he can indicate the number of curves done at each level it could save the rest of us a lot of ECM work that has no chance of finding a factor.
petrw1 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bug in generating ECM work for small exponents monsted PrimeNet 6 2019-09-28 03:25
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve mickfrancis Factoring 2 2016-05-06 08:13
P-1 on small exponents markr PrimeNet 18 2009-08-23 17:23
256KB L2 limited to small exponents, but 8MB L3 xorbe Information & Answers 2 2009-02-08 05:08
New "small" exponents available Prime95 PrimeNet 6 2006-05-21 15:38

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

Sat Aug 15 11:39:16 UTC 2020 up 2 days, 8:14, 0 users, load averages: 1.17, 1.35, 1.53

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.