View Single Post
Old 2020-06-28, 04:40   #4
Oct 2008

2×5 Posts

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.

Smooth: 0.89%
Containing 1 Large Prime: 12.10%
Containing 2 Large Primes: 65.00%
Containing 3 Large Primes: 22.01%

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