mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-06-27, 16:51   #1
patrickkonsor
 
Oct 2008

10102 Posts
Default Useless Accomplishment: RSA-140 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 RSA-140. This is a semi-prime with 140 decimal digits or 463 binary bits.

Note that RSA-140 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.
patrickkonsor is offline   Reply With Quote
Old 2020-06-27, 17:02   #2
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

2×5,101 Posts
Default

Quote:
Originally Posted by patrickkonsor View Post
As I am bored during the pandemic, I decided to revisit my quadratic sieve implementation from 10 years ago, and successfully factored RSA-140. This is a semi-prime with 140 decimal digits or 463 binary bits.

Note that RSA-140 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.
Congratulations.

It took us more like six months for the C135 IIRC.
xilman is online now   Reply With Quote
Old 2020-06-28, 03:06   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1100110011002 Posts
Default

Quote:
Originally Posted by patrickkonsor View Post
As I am bored during the pandemic, I decided to revisit my quadratic sieve implementation from 10 years ago, and successfully factored RSA-140. This is a semi-prime with 140 decimal digits or 463 binary bits.

Note that RSA-140 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.

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 as-is? How do you split the TLPs? Was it ECM or mpqs or something else?

In any case, very nice work!
bsquared is offline   Reply With Quote
Old 2020-06-28, 04:40   #4
patrickkonsor
 
Oct 2008

2·5 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 as-is? How do you split the TLPs? Was it ECM or mpqs or something else?

In any case, very nice work!
I'm happy to share any info you'd like.

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 RSA-100, 110, 120, 129, and 130 so I could optimize as I went along.
patrickkonsor is offline   Reply With Quote
Old 2020-06-28, 19:46   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by patrickkonsor View Post
As I am bored during the pandemic, I decided to revisit my quadratic sieve implementation from 10 years ago, and successfully factored RSA-140. This is a semi-prime with 140 decimal digits or 463 binary bits.

<snip>

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.
Impressive.
R.D. Silverman is offline   Reply With Quote
Old 2020-06-29, 14:10   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

327610 Posts
Default

Quote:
Originally Posted by patrickkonsor View Post
I'm happy to share any info you'd like.

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 RSA-100, 110, 120, 129, and 130 so I could optimize as I went along.
Thanks!

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 127-bit barrier. I'll have to try that out.
bsquared is offline   Reply With Quote
Old 2020-06-29, 14:53   #7
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

2×5,101 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
It might just be possible for me to dig out some ~20 year old records of my prior experiments with TMPQS as I then called it. Some of them may exist only in a paper notebook.

Bear in mind that great progress has been made since those days in the post-sieving steps (we didn't use re-sieving either) and so any numbers I can dig up may be of dubious utility.
xilman is online now   Reply With Quote
Old 2020-06-29, 21:40   #8
patrickkonsor
 
Oct 2008

2·5 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
In my experiments 2LP is clearly faster for RSA-100 and RSA-110. I've done a lot of experiments with RSA-120 and 3LP has always seemed faster, but I'm going to run some more tests to see if I can get 2LP to be competitive. Beyond 120 digits I'm confident that 3LP is faster.

Here are the parameters I've used with the fastest factorizations of each size, but they're not necessarily optimal:

RSA-100
FB Size: 100K
Sieve Size: 2MB
Large Primes: 2
Large Prime Bound: 200x
Sieve Cutoff 1: 104 bits
Sieve Cutoff 2: 59 bits

RSA-110
FB Size: 200K
Sieve Size: 4MB
Large Primes: 2
Large Prime Bound: 400x
Sieve Cutoff 1: 94 bits
Sieve Cutoff 2: 79 bits

RSA-120
FB Size: 245K
Sieve Size: 6MB
Large Primes: 3
Large Prime Bound: 100x
Sieve Cutoff 1: 116 bits
Sieve Cutoff 2: 75 bits

RSA-130
FB Size: 550K
Sieve Size: 20MB
Large Primes: 3
Large Prime Bound: 100x
Sieve Cutoff 1: 130 bits
Sieve Cutoff 2: 79 bits

RSA-140
FB Size: 1.3M
Sieve Size: 20MB
Large Primes: 3
Large Prime Bound: 99x
Sieve Cutoff 1: 146 bits
Sieve Cutoff 2: 81 bits
patrickkonsor is offline   Reply With Quote
Old 2020-06-29, 22:48   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by patrickkonsor View Post
In my experiments 2LP is clearly faster for RSA-100 and RSA-110. I've done a lot of experiments with RSA-120 and 3LP has always seemed faster, but I'm going to run some more tests to see if I can get 2LP to be competitive. Beyond 120 digits I'm confident that 3LP is faster.
It does not matter!! NFS is faster!
R.D. Silverman is offline   Reply With Quote
Old 2020-06-29, 23:11   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×32×7×13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It does not matter!! NFS is faster!
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.
bsquared is offline   Reply With Quote
Old 2020-06-29, 23:21   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
My reply was to "Beyond 120 digits...."
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
Quadratic Sieve by Hand Sam Kennedy Factoring 20 2013-01-09 16:50
Finding B in Quadratic Sieve paul0 Factoring 3 2011-09-22 17:12
Possible improvement of quadratic sieve Random Poster Factoring 4 2010-02-12 03:09
Quadratic Sieve in wikipedia.de ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 08:33.

Sat Aug 15 08:33:33 UTC 2020 up 2 days, 5:09, 0 users, load averages: 1.66, 1.83, 1.96

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.