Introduction
PSIQS is an open source Java package for integer factorization, and the fastest Java factoring program I am aware of.
Nonetheless it should be quite readable as well.
The package was named after the most powerful algorithm it contains, a Parallel SIQS implementation.
Other factor algorithms in the package are trial division, Lehman's method, SquFoF, PollardRho and CFrac.
In the background it features many good implementations of algorithms like sqrt and n.th root, power test,
TonelliShanks, KnuthSchroeppel multipliers and more.
Since version 4.0, PSIQS is published under GPL3.
Get it
Running the jar
You need Java 1.8. The executable jar file can be run in two forms:
 Without parameters you will be asked to insert factor arguments on standard input:
java jar psiqs4.0.jar
 Passing commandline parameters:
java jar psiqs4.0.jar [t <numberOfThreads>] <numberToFactor>
It may be favorable to specify a few JVM options: First it is necessary
to give it enough memory to be able to factor big numbers; and second one should configure
the garbage collector appropriately. 4 GB of RAM are more than necessary to factor 340 bit numbers,
but typically I am using something like
java Xmx12G XX:NewSize=128M XX:MaxNewSize=128M XX:+UseConcMarkSweepGC jar psiqs4.0.jar
The sources
To build the project from the sources, just create a plain Java project, extract the contents
of psiqs4.0src.zip to the root folder of the project, make sure that 'src' is the source folder
of your project, and add the log4j and junitjars from the libfolder to your classpath.
The sources are stuffed with comments.
The best starting points to explore it and in particular the quadratic sieve implementations are the classes
de.tilman_neumann.math.factor.FactorizerTest
de.tilman_neumann.math.factor.CombinedFactorAlgorithm
de.tilman_neumann.math.factor.siqs.SIQS
de.tilman_neumann.math.factor.psiqs.PSIQS_U
The larger algorithms have a plugin structure for their most important components.
This allows us for example to create a new implementation of the sieve stage only, plug it into
the SIQS class, and compare the performance of the new vs. old sieve stage implementation using
class FactorizerTest. Many components come already with several implementations, but typically
only one of them  the fastest  is really required. I did not bother creating a class hierarchy
in such cases; a diff shows us as quickly where the changes are. Slower implementations are
maintained because they are typically simpler, hence better apt to explain what a component should
actually be doing.
Speed
PSIQS 4.0 has the fastest quadratic sieve implementation in Java that I am aware of.
Look here
for a performance comparison with Dario Alperns ECM/SIQS implementation and Yafu 1.34.5.
Credits
My dearest thanks go to Dario Alpern for the permission to use his BlockLanczos solver, and
to Graeme Willoughby for his great comments on the BigInteger algorithms in the SqrtInt, SqrtExact, Root and PurePowerTest classes.
Contact
I would be happy about any comments or suggestions sent to
Tilman.Neumann(at)web.de
