D. J. Bernstein
Integer factorization


Psibound quickly computes lower and upper bounds on the distribution of smooth integers. I have a paper explaining the method.


The current version of Psibound requires an x86 machine, such as a Pentium III or (for better speed) an Athlon. It will not compile on non-x86 machines.

Download primegen-0.97.tar.gz, zpfft-0.50.tar.gz, and psibound-0.50.tar.gz in the same directory. Compile everything as follows:

     gunzip < primegen-0.97.tar.gz | tar -xf -
     ( cd primegen-0.97; make )
     gunzip < zpfft-0.50.tar.gz | tar -xf -
     ( cd zpfft-0.50; make )
     gunzip < psibound-0.50.tar.gz | tar -xf -
     cd psibound-0.50


For lower bounds and upper bounds on the distribution of 1000-smooth integers:
     ./psibound 1000 0 > 1000.0
     ./psibound 1000 1 > 1000.1
The current psibound program takes roughly 35 billion Pentium-II cycles, i.e., 100 seconds on a Pentium II-350, using 38 megabytes of memory, to produce 10 megabytes of output.

The output file 1000.0 contains 262144 lines showing lower bounds on Psi(x,1000) for various values of x. For example, the line

     232800 776 3316969875331297976743493363095454174822048
says that Psi(2^(232800/776),1000) is at least 3.31696*10^42. The output file 1000.1 contains 262144 lines showing upper bounds; for example,
     231300 771 3352333995371428390153438494245232797204720
says that Psi(2^(231300/771),1000) is at most 3.35234*10^42.

You can feed the output of psibound through

     ./rho 1000
to obtain lines such as
     2.037036e+90 1.000000e+03 3.010300e+01 1.945013e-50 1.645692e-48 84.610837
showing the first input to Psi, the second input to Psi, the ratio of the logs of the inputs, Dickman's rho function evaluated at that ratio, the approximate Psi output divided by the floor of the first input, and the ratio between the approximate Psi output and Dickman's rho function times the floor of the first input.