View Single Post
Old 2019-05-16, 11:34   #6
May 2019

23·3 Posts

The large primes I referenced were remaining prime factors of x^2-n larger than the factor base bound.
Ah, right. Yes, I'm doing that, but have not set a limit for accepting them. Any value that is not 1 after trial division is saved, and future remainders are checked against it, and merged if they match.

My implementation never goes below 6 factors per A. The factors get smaller but it is worth it to need less As.
A greater number of A-factors decreases the number of As necessary?

My implementation filters the factor base for primes between 400 and 4000 (call them "candidates"), and accumulates random candidates until their product is greater than the "tipping point" (sqrt((max-candidate - min-candidate) / 2)). It generates these until there are 30 that fall within plus-or-minus 10% of the ideal A, and chooses the one with the least error. In practice, the error of the A is 1% or less. It's not the fastest method, but the results are good (insofar as the obtained A is close to the ideal A) and the code is very clean—this sort of thing is quite legible and idiomatic in Clojure.

I tried an alternate approach (as described in some other paper) to generate lexicographic combinations for the first `s-2` A-factors and find the best-fitting product log for the last pair of A-factors. But it was much slower and very complicated.

For 50 digits, my factor base bound is 60k... For each polynomial I sieve a range of 600k.
Wow, those numbers are very different from mine. (To be fair, the Python MPQS I adapted used parameters that are quite different to what I read in the papers, but the weird parameters worked initially and the ones in the papers didn't).

I just generated a random 50-digit semiprime (from two equal-sized factors) (55720182748350551450373114705225729163236062899069). My MPQS generates these parameters:

B = 5*(log_10(N))^2 ~= 12373.32, which ends up yielding a factor base of...
#F = 725 primes, before including -1, so looking for 727 relations
M = 60 * #F = 43500 (so sieving over a range of 87000 in total b/c positive & negative)

75s with MPQS.

For SIQS I am using the #F parameter from msieve, and using that rather than B to constrain the factor base. So, for a 50-digit number, that's 1200 primes (excluding -1). Many As are not generating smooths—sometimes even 10 in a row go by without any new smooths.

Edited to add: I just switched out my parameters for yours in my MPQS and it did not make a huge difference—71s vs 75s—so that is indeed implementation-dependent. Interesting!

Last fiddled with by tabidots on 2019-05-16 at 11:54
tabidots is offline   Reply With Quote