mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

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

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!

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

52 Posts
Default

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

2·3·11 Posts
Default

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

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.