SIQS has unstable behaviour on small numbers about java-math-library HOT 2 CLOSED

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.

from java-math-library.

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.

from java-math-library.