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:

The output is a series of smaller factorization problems:

If you feed the output through toy again, you'll get

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