A small factoring program

Yamato · 2007-11-21, 21:23

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!

factor_linux_64bit.tar.gz
factor_linux_32bit.tar.gz
factor_windows_32bit.zip

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.

vector · 2007-11-21, 21:51

This program does not run under windows XP.

Yamato · 2007-11-21, 23:29

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

2007-11-21, 21:23	#1
Yamato Sep 2005 Berlin 102₈ Posts	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! factor_linux_64bit.tar.gz factor_linux_32bit.tar.gz factor_windows_32bit.zip 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Command-line program for factoring small numbers	James Heinrich	Software	22	2011-08-29 16:35
Where is a factoring program?	Siemelink	Software	2	2006-01-10 20:30
small matlab program for results file	tom11784	Programming	2	2003-11-29 14:30
Small win32 program, range of time to do a TF	dsouza123	Programming	1	2003-10-09 16:04
Small win32 program to show system uptime and more	dsouza123	Programming	0	2003-09-28 22:28

2007-11-21, 21:51	#2
vector Nov 2007 home 5² Posts	This program does not run under windows XP.

2007-11-21, 23:29	#3
Yamato Sep 2005 Berlin 2·3·11 Posts	Under WinXP, type "factor <number>" without "./" at the beginning (I forgot to mention). Then it should work.