Useless Accomplishment: RSA-140 Factorization with Quadratic Sieve

[patrickkonsor]

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.

[xilman]

Originally Posted by patrickkonsor

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.

[bsquared]

Originally Posted by patrickkonsor

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!

[patrickkonsor]

Originally Posted by bsquared

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.

[R.D. Silverman]

Originally Posted by patrickkonsor

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.

[bsquared]

Originally Posted by patrickkonsor

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.

[xilman]

Originally Posted by bsquared

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.

[patrickkonsor]

Originally Posted by bsquared

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

[R.D. Silverman]

Originally Posted by patrickkonsor

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!

[bsquared]

Originally Posted by R.D. Silverman

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.

[R.D. Silverman]

Originally Posted by bsquared

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...."