All rights reserved.
Tilman Neumann 2007-2017

Introduction

PSIQS is an open source Java package for integer factorization. I named it after the most powerful algorithm it contains, a Parallel SIQS implementation. Other factor algorithms included in the package are SquFoF, CFrac and PollardRho. In the background it features many state-of-the-art algorithms like Tonelli-Shanks or Knuth-Schroeppel multiplier determination. Besides it brings some classes that simplify the development and testing of factor algorithms, like a test data generator and a performance test capable of comparing several algorithms.

The main development goals have been stability and to make the algorithms easy to understand. Because of the supposed educational value I consider the source distribution as the important one. However, to demonstrate quickly that it works, there is also an executable jar file having a simple command-line interface.

In release 02.00 and 02.01, tuning the performance of SIQS and PSIQS has become another major goal. Indeed it has become the fastest Java program for integer factorization that I am aware of. See below how it compares to other programs.

Get it

Running the jar

You need Java 1.8. The executable jar file can be run in two forms:

  1. Without parameters you will be asked to insert factor arguments on standard input:
    java -jar psiqs02.01.jar
  2. Passing command-line parameters:
    java -jar psiqs02.01.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 psiqs02.01.jar

The sources

To build the project from the sources, just create a plain Java project, extract the contents of psiqs02.01-src.zip to the root folder of the project, make sure that 'src' is the source folder of your project, and add the log4j- and junit-jars from the lib-folder 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

The larger algorithms have a plug-in 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.

Current speed...

PSIQS 02.01 is about three times faster than release 01. At least for large numbers (250, 300 bit and more) it is also about twice as fast as Dario Alpern's Java Siqs implementation. On the other hand, the C-written Yafu program is more than three times faster than PSIQS 02.01.

Look here for a recent performance comparison.

...and how to make it faster

In Java, there are not so many options left. Thanks to Dario Alpern's permission there is now a Block-Lanczos solver. I also explored segmented sieves and sieving with prime powers, which gave no notable improvement. A small improvement could be obtained by reducing the number of short-living objects generated by SIQS. Otherwise, all I can think of now is that somebody comes up with some great ideas, or an GNFS implementation (which is quite a challenge).

A larger speed-up could be expected from a port of the sieve or the complete (P)SIQS to C(++). C is not only notably faster in such high-performance applications, but in C we could as well expect the segmented sieves to have some impact, and use some tricks not available in Java, like byte[] to long[] conversion in the sieve collect phase.

Credits

My dearest thanks go to Dario Alpern for the permission to use his Block-Lanczos 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