SIQS has unstable behaviour on small numbers

[AlexMaleyko]

Hello,
I am iterating through a large sequence of primes starting from 5 and ending near 10 bln. and for specific primes call SIQR.factor(prime - 1). But after the very first iterations the loop hangs. After a short debugging found out that when SIQR.factor() is given 180 as a parameter, the algorithm behaves unpredictably. It sometimes returns the correct factorization (but it takes several seconds), but almost every time hangs forever. Probably there is a bug in factor_recurrent.
the code I use is as follows:
SIQS siqs = new SIQS(0.32F, 0.37F, null, 0.16F, new PowerOfSmallPrimesFinder(), new SIQSPolyGenerator(), new Sieve03g(), new TDiv_QS_1Large_UBI(), 10, new MatrixSolver01_Gauss(), false); siqs.factor(BigInteger.valueOf(180))
Are the parameters correct for the range of numbers specified above?

[TilmanNeumann]

This is typical for SIQS implementations. Once I had a version that was stable for numbers down to 12 or 10 bits. But any adjustment to gain more speed may change that.

The current single-threaded SIQS should be stable for N <= 55 bit or less. That is sufficient because there are better algorithms for N <= 55 bit. Using CombinedFactorAlgorithm.factor(...) will make use of better algorithms for small numbers.

PSIQS is another case. It may not be 100% stable for N<100 bit or so. The reason is that Java's synchronize{} blocks are not 100% atomic. I have not found a way yet to get around that problem. But again, it is not a big problem because the single-threaded SIQS is faster than PSIQS for "small" N. E.g. SIQS is faster than PSIQS(6 threads) for N<= 150 bit. Creating and starting (sieve) threads seems to be quite expensive.

[TilmanNeumann]

Thanks to David Artizada to point out that the PSIQS issue I mentioned above was probably a true deadlock. Indeed it was, and that part of the previous comment nonsense. As it turned out, my synchronization approach was basically ok; but for small N, the sieve threads were so fast that they cued to take the aqPairBuffer lock. Hence they used up all a-parameters before the control thread managed to collect the relations and start the linear algebra step.

My solution was to move the relation check into the sieve threads. That's not the optimal starting position if PSIQS should ever be converted into a distributed program, but I think that would require so many changes of the parallelization scheme that it hardly matters.

All that remains in this issue is the point that both SIQS and PSIQS may not be capable to factor small numbers because there are not enough a-parameters. This is typical for SIQS implementations, though.