View Single Post
Old 2019-05-16, 02:45   #1
May 2019

23×3 Posts
Question SIQS diagnostics

Hello all, this is my first post on the forum.

I recently got interested in factoring while implementing some number theory-related programs in Clojure to teach myself the language. As far as algorithms go, I have managed to get as far as MPQS. My implementation is hardly competitive (the speed of the Alperton calculator blows my mind), but for a language that is not exactly known for speed, I'm quite satisfied with it right now.

My MPQS implementation is based on this Python implementation (and it's faster than the CPython version—don't know about PyPy) and a bunch of papers.

I recently tried to "upgrade" my MPQS to SIQS using Contini's paper and this Python implementation, but it's very slow.

So far my MPQS beats the Python MPQS. But the Python SIQS (which was programmed by someone else) is slower than that, and my SIQS is slower still, for the same numbers. For example, a number that my MPQS could factor in a couple of seconds takes my SIQS 30 seconds or more.

In both the Clojure and Python implementations, it seems like it has to run through way too many polynomials to pick up enough smooth relations. It's not uncommon for an entire cycle through a polynomial with a unique "a" and all of its "b"s to generate no smooth relations.

If SIQS is supposed to be massively faster than MPQS, shouldn't just a couple of "brand-new" polynomials be enough? (Brand-new meaning a new "a" coefficient.)

I did come across this thread where people mentioned that there was a typo in Contini's thesis. However, it is not clear to me what the typo actually is (and when I fiddled with the signs, it didn't make a difference).

So my basic question is, what kind of gotchas should I look for with the polynomials to make sure they can capture as many smooth relations as possible? I have already verified that b^2 or (a - b)^2 is congruent to N mod a for each b.

Other details of my implementation: In the sieving stage, I am ignoring small primes below some threshold, which is adjusted to compensate. The parameters for this were taken from the Python MPQS and they contribute to a significant speedup in SIQS as well.

The Python SIQS uses a Monte Carlo method to generate the factors of "a", with the candidate pool restricted to primes between 400 and 4000. I've kept the same parameters in my implementation (tinkering with these bounds seems to make it take more time to generate an acceptable "a"—Contini's paper mentions that his minimum prime factor of "a" was >2000, but this seems crazy to me).

As a side note, I'm testing on semiprimes that are considered "small" in the factoring world—40 to 50 digits—because I don't have time to sit around all day waiting for my program to finish 😅

tabidots is offline   Reply With Quote