View Single Post
Old 2020-06-28, 03:06   #3
bsquared's Avatar
Feb 2007

2×5×7×47 Posts

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