mersenneforum.org TF small exponents on GPU?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-10-12, 01:23 #1 mnd9   Jun 2019 Boston, MA 3810 Posts 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?
 2019-10-12, 01:44 #2 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 156048 Posts 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.
 2019-10-12, 03:21 #3 GP2     Sep 2003 2,579 Posts 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.
2019-10-12, 03:25   #4
GP2

Sep 2003

2,579 Posts

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

 2019-10-12, 03:58 #5 masser     Jul 2003 wear a mask 2·17·41 Posts Is there a way to perform ECM curves on a GPU?
2019-10-12, 04:07   #6
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

11011100001002 Posts

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

2019-10-12, 05:35   #7
GP2

Sep 2003

2,579 Posts

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

2019-10-12, 08:26   #8
hansl

Apr 2019

5·41 Posts

Quote:
 Originally Posted by GP2 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 Here is the ECM Report for exponents under 10,000.
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.

2019-10-12, 12:33   #9
storm5510
Random Account

Aug 2009
U.S.A.

2×3×227 Posts

Quote:
 Originally Posted by masser Is there a way to perform ECM curves on a GPU?
This is something I've hoped for a long time. One day, perhaps...

2019-10-12, 14:45   #10
GP2

Sep 2003

A1316 Posts

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

 2019-10-13, 03:20 #11 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 10000111011112 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post monsted PrimeNet 6 2019-09-28 03:25 mickfrancis Factoring 2 2016-05-06 08:13 markr PrimeNet 18 2009-08-23 17:23 xorbe Information & Answers 2 2009-02-08 05:08 Prime95 PrimeNet 6 2006-05-21 15:38

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

Sat Aug 15 11:11:35 UTC 2020 up 2 days, 7:47, 0 users, load averages: 1.69, 1.72, 1.58