All rights reserved.
Tilman Neumann 2007-2016

Introduction

PSIQS is a new open source Java package for integer factorization. I named it after the most powerful algorithm it contains, a Parallel SIQS implementation. But actually it is more than that, including a whole bunch of factor algorithms like SquFoF, CFrac and the three quadratic sieve variants (basic QS, MPQS, SIQS). 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, originally I planned a source distribution only. However, to demonstrate quickly that it works, in the last minute I also created an executable jar file having a simple command-line interface.

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 psiqs01.02.jar
  2. Passing command-line parameters:
    java -jar psiqs01.02.jar [-t <numberOfThreads>] <numberToFactor>

With small factor arguments the second option may appear a bit sluggish, because all static initializers must be executed for each number; but entering a bigger factor argument like a 200 bit number will show that the performance is not that bad.

It is also 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. Typically I am using something like

java -Xms12G -Xmx12G -XX:NewSize=4G -XX:MaxNewSize=4G -XX:+UseConcMarkSweepGC -jar psiqs01.02.jar

The sources

To build the project from the sources, just create a plain Java project, extract the contents of psiqs01.02-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.qs.QS
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 QS 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...

The (P)SIQS realization in this package has most state-of-the-art algorithms, and they have been implemented quite carefully. But it is not complete yet, and optimization has only arrived at a medium level. Nevertheless it is almost as fast as Dario Alpern's SIQS-implementation (and sometimes faster); I have never seen a difference greater than factor 1.5.

On my Sandybridge i7-notebook with 16 GB RAM and with 6 threads, PSIQS requires approximately 3s for 200 bit numbers, 2 minutes for 250 bit numbers and 1.5 hours for 300 bit numbers. The used test numbers N had two factors, the smaller factors having a uniformly distributed bit-length between ld(N)/3 and ld(N)/2.

...and how to make it faster

There are many options. First of all, implement the things still missing in the SIQS implementation:
  • Sieving with prime powers.
  • Currently there is only a Gaussian solver. A Block-Lanzcos or Block-Wiedemann solver would be a nice improvement, in particular for the multi-threaded PSIQS.

Next, it would be important to reduce the number of short-living objects generated by SIQS. This work has already been started using the mutable class UnsignedBigInt in the trial division stage, resulting in a significantly reduced garbage collection load. But the garbage collector is still active, and since creating all those objects may be much more expensive than the garbage collection itself, there is more to do about that.

Third, since SIQS spends about 70% of its time in it, it would be a big improvement to optimize the sieve stage to a high level. A nice approach would be to implement it in C(++), e.g. using JavaCpp. Once we have a C(++)-implementation, we can apply several tricks not possible in Java, like the explicit use of SIMD-features of modern CPUs or casting byte-arrays to long-arrays for the collect phase of the sieve.

Last not least, a GNFS implementation is of course desirable, too. It is possible that the existent abstraction of the PolyBuilder/Poly classes helps on that way.

Contact

I would be happy about any comments or suggestions sent to
Tilman.Neumann(at)web.de