A small factoring program
 

I've found the time to write an own program for prime factorization. It works similar to the Unix-built-in "factor" command, but is not restricted in the size of the input. It's small but (i hope) not slow, please try it out!

[url=http://www2.informatik.hu-berlin.de/~schoenbe/factor_linux_64bit.tar.gz]factor_linux_64bit.tar.gz[/url]
[url=http://www2.informatik.hu-berlin.de/~schoenbe/factor_linux_32bit.tar.gz]factor_linux_32bit.tar.gz[/url]
[url=http://www2.informatik.hu-berlin.de/~schoenbe/factor_windows_32bit.zip]factor_windows_32bit.zip[/url]

Usage: Type
./factor <number>
in the command line and you will get the full factorization of <number>, e. g.

./factor 400000000000000000000000000000000000001
89 * 21929 * 710777042881 * 288348545377013952641

The program uses the following methods:
1. trial division to remove trivial factors < 10^2
2. Pollard Rho for small factors < 10^6 (x^2 + 1 with random start value)
3. Lenstra ECM for factors > 10^6 (with automatically increasing B1/B2)

The program uses Miller-Rabin for primality testing so it should be unlikely that a non-prime will be displayed without the number being recognized as composite.

It's possible to find hidden prime factors of 25-35 digits within a reasonable amount of time (it essentially depends on the input length and the luck). Moreover it's easy to use it in parallel. Some randomized tests are run so the program will not compute the same.

So try it out, i hope it works properly.

This program does not run under windows XP.

Under WinXP, type "factor <number>" without "./" at the beginning (I forgot to mention). Then it should work.