View Single Post
Old 2020-06-29, 14:10   #6
bsquared's Avatar
Feb 2007

3·23·53 Posts

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.

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.

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.

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