readme

Smooth Subsum Search: Fast Integer Factorization in Python

Smooth Subsum Search (SSS) is a new algorithm for collecting so-called smooth values of integer polynomials.
Finding such values is an important part of the currently best integer factorization algorithms, 
such as the Quadratic Sieve and the General Number Field Sieve. The current implementation of SSS can be used
for factoring large integers in Python, and is around 5 to 7 times faster than comparable implementations of 
the Quadratic Sieve. 

This repository contains the source code of the algorithms SSS and SSSf as described in Section 3 of the paper 
"Smooth Subsum Search: A Heuristic for Practical Integer Factorization", which appeared in Int. J. Found. Comp. Sc.
(DOI: https://doi.org/10.1142/s0129054123500296, Preprint: https://arxiv.org/abs/2301.10529). In addition, 
two Python scripts for the Self-initializing Quadratic Sieve from other packages are included:

1) psiqs.py contains the implementation of the primefac-package (https://pypi.org/project/primefac/)
2) ssiqs.py contains the implementation of the sympy-package (https://fossies.org/linux/sympy/sympy/ntheory/qs.py)

The file test.py has been used for comparing these approaches and obtaining the results presented in 
Section 4 of the paper.