Go Back > Factoring Projects > Factoring

Thread Tools
Old 2007-11-21, 21:23   #1
Yamato's Avatar
Sep 2005

1028 Posts
Default 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!


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.
Yamato is offline   Reply With Quote
Old 2007-11-21, 21:51   #2
vector's Avatar
Nov 2007

52 Posts

This program does not run under windows XP.
vector is offline   Reply With Quote
Old 2007-11-21, 23:29   #3
Yamato's Avatar
Sep 2005

2·3·11 Posts

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

Thread Tools

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

All times are UTC. The time now is 00:02.

Mon Mar 8 00:02:07 UTC 2021 up 94 days, 20:13, 0 users, load averages: 2.29, 2.23, 2.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.