no-factor-base (NFB) factorization

Factorization C/C++ NFB lib, the no-factor-base sub-exponential general purpose algorithm

In number theory, integer factorization is the decomposition of a composite number into a product of
smaller integers. The hardest instances of factorization problems (for currently known techniques) are semiprimes, the
product of two prime numbers, when they are both large, randomly chosen, and about the same size (but not too close).

There is a class of sub-exponential algorithms (e.g. Dixon algorithm, General number field sieve, Quadratic sieve) that
are based on the congruence of squares method. These methods search for a set of quadratic residues mod N which are B-smooth,
i.e. all prime factors of the quadratic residues are less than some bound B. To check if the quadratic residue mod N is
B-smooth, one needs to perform trial divisions of this residue by all primes less than B. These primes constitute the factor
base for a factorization algorithm.

There are some issues about using factor base:
- some quadratic residues may be useful for factorization, but they are excluded as not B-smooth
- one cannot know in advance which factors in a factor base are useful, i.e. which of them can divide at least one quadratic
residue mod N. With this information, one would rather use a greater than B prime which is a common divisor of quadratic
residues mod N than spend time on trial divisions by all primes less than B.

The use of factor base was introduced in 70s to run factorization under severe limitations in RAM. Now this idea seems obsolete, but
it still shapes the algorithms and even the concepts of the number theory.

The no-factor-base (NFB) method uses GCD function to find common divisors of the quadratic residues modulo n. As a result,
the heuristic complexity of L(1/2, x) algorithms like Dixon's algorithm or quadratic sieve algorithm improves to L(2/5, 2),
and the complexity of L(1/3, x) algorithms improves to L(4/15, 2).

The code includes an example of a simple strategy of searching quadratic residues mod N that are not B-smooth but can
be effectively used for factorization. The example exhibits L(4/15, 2) complexity.

author

(a) pavelmalyshkin