D. J. Bernstein

Integer factorization

# smallfactors

If you have y/log^O(1) y integers,
each with at most log^O(1) y bits,
then you can find all the small prime factors of each integer
in time log^O(1) y per integer.
This speeds up
integer factorization, discrete logs, class-group computations, etc.
I have a
paper
explaining the method,
and a
newer paper
on an exponent improvement.
smallfactors
is a serious implementation, using
Zmult
for fast multiplication and
streamlined Newton
for fast 2-adic division.
Watch this space for the first release.

## Toy code

toy.c
is a simple implementation that uses
GMP for arithmetic.
I used GMP 3.0.1 plus the division patch.
Beware that GMP allocates large temporary variables on the stack.
If the stack runs out of space,
the kernel kills the program with a segmentation fault.
Make sure to remove the stack-size resource limit before using GMP: e.g.,

unlimit stacksize

under csh.
To compile `toy.c`, type

gcc -o toy toy.c -lgmp

To run it, type
./toy < in > out

The input file is series of factorization problems.
Each problem is a list of primes, a 0,
a list of integers to be factored, and a 00:
2
3
5
0
23456
34567
00

The output is a series of smaller factorization problems:
2
0
23456
00
2
0
34567
00

If you feed the output through `toy` again,
you'll get
2
0
23456
00
0
34567
00

For large problems you may have to run `toy` several times
before the output stabilizes.