20101102, 13:18  #1 
Nov 2003
1110100100100_{2} Posts 
New 70 digit factor
Lenstra et.al. just announced finding a 70 digit factor of 2^1237  1.
This lies outside of the current Cunningham table. I wish they would make a pass at the Cunningham 2+ numbers....... 
20101102, 14:54  #2 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10253_{8} Posts 
It is listed in the Factor DB. It is 2538207129840687799335203259492870476186248896616401346500027311795983. The cofactor is 303 digits and is composite.
Congratulations to all involved for a huge factor! It is the third largest ECM factor yet. 
20101102, 15:07  #3 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
10011101001_{2} Posts 
That was my favourite number, man!
p70 = 2538207129840687799335203259492870476186248896616401346500027311795983
from M1237 by Lenstra et. al. by using ECM?, rather within that way After M1061, this was the smallest Mersenne number with no known factors at all That Remaining cofactor c303 is still composite, as yet. enough May be that it was based upon my suggestion, atleast? M1277 is that next Mersenne number with no known factors at all, after that only M1619. M1277 I guess that it may have a much larger enough prime factor, as it is closer to that prime number: M1279. Similarly as it was that case for M521, which is prime, M523 has a prime factor, that splits up into p69.p90 Do you know about any place, at that point, where this new result, along with that sigma value, curve counts, computational efforts, etc. have been posted up within any paper at some given conference/journal? Where was that announced? How > through private mail, or personally, to whom? Then, who was that person inserting up with that result into that factor database? Last fiddled with by Raman on 20101102 at 15:34 
20160118, 20:32  #4 
Oct 2007
Manchester, UK
1338_{10} Posts 
Forgive me for resurrecting an old thread, but I am curious to know if the factorisation of M1237 / p70 (a c303) with SNFS is now within the realm of possibility for a dedicated amateur (or possibly as a group project)?
I have some experience of factoring numbers in the low 200's of digits, but I don't know how the amount of memory required increases for much larger numbers. Alternatively there is the slightly easier number of M1213 / (327511 * p63), which is a c297. 
20160118, 23:51  #5  
(loop (#_fork))
Feb 2006
Cambridge, England
6,379 Posts 
Quote:
Kleinjung / Bos / Lenstra did 2^11991 with the final step involving a 270M matrix which took 170 days on a substantial (couple of millions of dollars worth of nodes) cluster at EPFL, and which would take decades on the fastest equipment I have access to. Last fiddled with by fivemack on 20160118 at 23:51 

20160119, 00:33  #6  
"Curtis"
Feb 2005
Riverside, CA
1001000010001_{2} Posts 
Quote:
Matrixsolving memory requirements roughly increase with the square of dimension, while siever memory requirement increases much more slowly (something on the order of a doubling every 150 add'l bits, assuming the CADO siever can do 2^18 by 2^17 sieve region). Something like 45GB per thread might be sufficient to sieve M1200M1300. You might also want to see what NFS@home (or the M1061 thread here) has for stats on M1061; 5 years later, that size of project might be possible for a forum group. M1200+ is just nuts. 

20160119, 02:53  #7 
Oct 2007
Manchester, UK
2×3×223 Posts 
Aha, I was not aware of this. I had thought that the known factors could reduce the difficulty of running SNFS, while still allowing one to take advantage of the special form of the number.
Purely as a thought experiment then, which would actually be easier, running SNFS on M1237 or running GNFS on the remaining c303 after dividing out the known p70? Would it be GNFS? I think I vaguely remember reading that SNFS can factor numbers ~50 digits larger than GNFS for roughly the same amount of work/time/other meaningful unit of measure. (I realise that running either on these numbers is not practical without an NSA sized budget, and perhaps not even then.) I will read more on the factoring efforts on M991 and M1061. 
20160119, 04:01  #8  
"Curtis"
Feb 2005
Riverside, CA
5^{3}·37 Posts 
Quote:


20160119, 04:13  #9  
"Curtis"
Feb 2005
Riverside, CA
5^{3}·37 Posts 
Quote:


20160119, 18:27  #10  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
16A3_{16} Posts 
Quote:
As far as I can see in the code there doesn't seem to a limit to the sieve region. 16GB is becoming much more possible as far a memory usage for all cores is concerned. 32GB is only around £100 now and 16GB is only £50 if we can make it squeeze in there. I wonder when it will be time for nfs@home to add the CADO siever for larger jobs. 

20160119, 23:09  #11 
"Curtis"
Feb 2005
Riverside, CA
5^{3}·37 Posts 
Tests on CADO by me (and fivemack, I believe) indicate the siever is 1530% slower than GGNFS when running the same parameters.
So, for big NFS@home projects, one may need to only make up that ~25% efficiency via larger largeprime bounds or 17eequivalent sieve area to make CADO more efficient. I expect GNFS220 might be big enough for CADO to be faster than ggnfs. I discovered the "params" folder in CADO last night, which has some suggested settings for a range of number sizes. Sometime soon I'll see about running I = 17, or 3 35bit large primes, or both as compared to ggnfs. Perusal of the RSA768 run they did showed they used I = 16, but that was likely a memory restriction as their sieve nodes either had 1GB or 2GB. They also used 40bit large primes (!!!). The notes say "parameters were optimized for 37LP, but we accepted up to 40 bit large primes." 64 billion raw relations later.... Last fiddled with by VBCurtis on 20160119 at 23:11 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factor a 108digit number  sweety439  Factoring  9  20161221 21:22 
73 digit ECM factor  akruppa  Factoring  103  20101127 20:51 
44digit factor found using ECM w/ B1=1e6 & B2=1e8  WVU Mersenneer  Factoring  8  20100424 17:01 
Probability of ndigit factor?  roger  Factoring  3  20070509 22:51 
160 digit factor found of 366 digit (PRP1)  AntonVrba  Factoring  7  20051206 22:02 