20200627, 16:51  #1 
Oct 2008
2×5 Posts 
Useless Accomplishment: RSA140 Factorization with Quadratic Sieve
As I am bored during the pandemic, I decided to revisit my quadratic sieve implementation from 10 years ago, and successfully factored RSA140. This is a semiprime with 140 decimal digits or 463 binary bits.
Note that RSA140 was factor many years ago with the NFS, which makes this mostly pointless, but I believe this should be the largest factorization ever with the quadratic sieve, as the past record appears to be 2,1606L.c135, which was 135 digits and 446 bits. The factorization took a bit under 6 days across 60 cores that were used sporadically, for a total of 5,959 core hours. All systems were Skylake based Core or Xeon. I used a factor base size of 1.3M, so I collected 1,337,268 relation cycles, which included 217,533 smooth relations and 1,119,735 combined relations from 24,281,191 partial relations with up to 3 large primes. 
20200627, 17:02  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2ACC_{16} Posts 
Quote:
It took us more like six months for the C135 IIRC. 

20200628, 03:06  #3  
"Ben"
Feb 2007
2·1,789 Posts 
Quote:
Congratulations, that's quite a feat! Can you give a few more details? What were the large prime bounds? Do you have any more statistics on the cycles, e.g., the percentage that used a TLP? It's been a while since I've browsed your code, did you make any changes/improvements first or did you just fire it up asis? How do you split the TLPs? Was it ECM or mpqs or something else? In any case, very nice work! 

20200628, 04:40  #4  
Oct 2008
A_{16} Posts 
Quote:
Large prime bounds: 1 Large Prime: 43081993 (26 bits) .. 4265117307 (32 bits) 2 Large Primes: 1856058120852049 (51 bits) .. 18191225642470932249 (64 bits) 3 Large Primes: 79962682970141129053657 (77 bits) .. 77587711323244967379634333443 (96 bits) Note that I didn't directly use the 96 bits 3LP max composite to adjust the sieve cutoffs, because then you spend all day factoring potential 3LP relations that end up having a relatively low chance of forming a cycle. I experimentally determined that 96  15 = 81 bits was the optimal value to adjust the sieve cutoffs. So the two sieve cutoffs were 146 bits in order to trial divide out the small factors, and 81 bits to factor the large primes. One novel idea I used to enable sieve cutoffs >127 bits is to effectively lower the precision of the factor base logs (and first sieve cutoff) by dropping the LSB, rather than being limited to a max cutoff of 127. Relations: Smooth: 0.89% Containing 1 Large Prime: 12.10% Containing 2 Large Primes: 65.00% Containing 3 Large Primes: 22.01% Cycles: Smooth: 16.27% Containing only 1LP relations: 8.39% Containing up to 2LP relations: 21.13% Containing up to 3LP relations: 54.21% To factor 2LP or 3LP composites I used SQUFOF for smaller composites, and ECM for larger composites or when SQUFOF failed. For ECM I tried up to 10 curves, and used B1=150 and B2=4000. I'm sure I could improve the ECM implementation. I made quite a lot of changes to my code compared to what I had in 2010. Professionally I work at Intel as a computer/software performance engineer, so a lot of my focus was on uarch optimizations, but I also did some higher level algorithmic improvements, and a lot of parameter tuning. I progressively factored RSA100, 110, 120, 129, and 130 so I could optimize as I went along. 

20200628, 19:46  #5  
Nov 2003
2^{2}·5·373 Posts 
Quote:


20200629, 14:10  #6  
"Ben"
Feb 2007
2·1,789 Posts 
Quote:
I have also been tinkering with the three large prime variation during this pandemic. I've mostly been focused on seeing if I can make QS faster in the upper end of the size range where it is currently still used, from about 90 to 100 digits. So far, TLP has not been helpful there. The crossover where it starts to become faster, at least in my implementation, is at about C110. Have you done similar crossover studies? I'd be interested in the parameters data you gathered for RSA 100, 110, 120, etc, as well, if you still have that available. Public data for TLP QS parameters, as far as I know, consists of this thread, Paul's paper, and a few threads of mine. [edit] p.s., I like your idea of reducing the precision of logp to get around the 127bit barrier. I'll have to try that out. 

20200629, 14:53  #7  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{2}×3×11×83 Posts 
Quote:
Bear in mind that great progress has been made since those days in the postsieving steps (we didn't use resieving either) and so any numbers I can dig up may be of dubious utility. 

20200629, 21:40  #8  
Oct 2008
2×5 Posts 
Quote:
Here are the parameters I've used with the fastest factorizations of each size, but they're not necessarily optimal: RSA100 FB Size: 100K Sieve Size: 2MB Large Primes: 2 Large Prime Bound: 200x Sieve Cutoff 1: 104 bits Sieve Cutoff 2: 59 bits RSA110 FB Size: 200K Sieve Size: 4MB Large Primes: 2 Large Prime Bound: 400x Sieve Cutoff 1: 94 bits Sieve Cutoff 2: 79 bits RSA120 FB Size: 245K Sieve Size: 6MB Large Primes: 3 Large Prime Bound: 100x Sieve Cutoff 1: 116 bits Sieve Cutoff 2: 75 bits RSA130 FB Size: 550K Sieve Size: 20MB Large Primes: 3 Large Prime Bound: 100x Sieve Cutoff 1: 130 bits Sieve Cutoff 2: 79 bits RSA140 FB Size: 1.3M Sieve Size: 20MB Large Primes: 3 Large Prime Bound: 99x Sieve Cutoff 1: 146 bits Sieve Cutoff 2: 81 bits 

20200629, 22:48  #9  
Nov 2003
1D24_{16} Posts 
Quote:


20200629, 23:11  #10 
"Ben"
Feb 2007
2·1,789 Posts 
For the C100, this is not true; or at least, it is close enough to be worth discussing. For the others, of course you're right. But everyone discussing here knows that already; we are optimizing our QS implementations anyway for fun.

20200629, 23:21  #11 
Nov 2003
2^{2}·5·373 Posts 
My reply was to "Beyond 120 digits...."

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
Finding B in Quadratic Sieve  paul0  Factoring  3  20110922 17:12 
Possible improvement of quadratic sieve  Random Poster  Factoring  4  20100212 03:09 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 