This page describes some software that I have written, (and some that I didnt write). And it can be downloaded and used for free! These programs do arithmetic and/or factoring with large integers. (The meaning of large varies from one program to another.) These programs run on Windows and OS/2.
Download (for Windows), version 2.0, last updated on February 6, 2003.
Download (for OS/2), Version 1.5, last updated on November 5, 2001.
fact.exe is a calculator-type program that runs in a command window on Windows 95 and later, or in an OS/2 command window on OS/2. In addition to calculating, it can (try to) factor a number using the try all divisors method.
Here is a write-up on how to use this program. There is also an example below showing how the program works.
Version 2.0 of fact.exe includes the modular inverse function. If e and z are integers, with gcd(e,z)=1 (gcd = greatest common divisor), then the modular inverse of e mod z is the integer d (between 1 and z) such that d * e = 1 mod z. fact.exe uses the \ (backslash) character for the modular inverse operator. For example:
d (meaning 99\1009) has the value 265, since 265*99 = 26235 = 1 mod 1009
Note: if gcd(e,z)>1, then e\z computes d such that d*e=g mod z, where g is gcd(e,z). In this case, there is more than one possible value for d, so you get one of the values. The program also displays a warning message that the gcd is greater than 1.
For example: gcd(6,8) = 2.
6\8 computes the value 7, which works since 7*6 = 42 = 2 mod 8.
The value 3 would also be acceptable, since 3*6 = 18 = 2 mod 8.
fac.exe is an old 16-bit program similar to fact.exe. However, it is limited to numbers up to about 2400 digits. This program may be useful if you are still using MS-DOS (without Windows) or if you are using Windows 3.1. Otherwise, fact.exe is recommended.
Here is a write-up on how to use this program. It is the same as the write-up for fact.exe above.
Shamus has placed factor.exe into the public domain. Their executable runs in a DOS (command) window on Windows 95/98/Me/NT/2000/XP. I downloaded the source code from their web site, made a few small changes, and compiled it for Windows 95 and later and for OS/2. Updated on October 7, 1999.
A version of factor.exe, which I call factor2.exe, works with larger numbers, up to about 280 digits. (Windows only, at present.)
An updated version of factor2.exe, called factorx.exe, tries an additional set of elliptic curves on numbers larger than 83 digits. Download it for Windows.
My factoring page has some information on the different factoring methods used by this program.
C:>fact > a=2^99-1? 633825300114114700748351602687=7*23*73*89*199*153649*599479*33057806959 > b=2^127-1 =170141183460469231731687303715884105727 > 3^(b-1)%b =1 > c=2^128+1 =340282366920938463463374607431768211457 > 3^(c-1)%c =47511664169441434718291075092691853899 > x=2^64+1,y=274177,z=x/y =18446744073709551617 =274177 =67280421310721 > y*z=-x =18446744073709551617 =0 > y 274177=PRIME > n=10^29/9 =11111111111111111111111111111 > n 11111111111111111111111111111=3191*16763*43037*62003*77843839397 >
You can put the number to be factored on the command line:
C:>factor 12345678910111213141516 first trying brute force division by small primes PRIME FACTOR 2 PRIME FACTOR 2 now trying 1000 iterations of brent's method finally - the multiple polynomial quadratic sieve - with large prime (*) using multiplier k= 1 and 57 small primes as factor base working... 54 trying... working... 55 trying... PRIME FACTOR 2507191691 PRIME FACTOR 1231026625769Or you can use -f to indicate a formula. (factor uses # for exponentiation.)
(C:\)factor -f 10#41+7 100000000000000000000000000000000000000007 first trying brute force division by small primes PRIME FACTOR 317 now trying 1000 iterations of brent's method PRIME FACTOR 141767 now trying william's (p+1) method phase 1 - trying all primes less than 10000 phase 2 - trying last prime less than 1000000 PRIME FACTOR 1287620401 PRIME FACTOR 1728135292692949031248613And another example:
(C:\)factor -f 10#50+11 100000000000000000000000000000000000000000000000011 first trying brute force division by small primes PRIME FACTOR 3 PRIME FACTOR 37 PRIME FACTOR 47 PRIME FACTOR 1367 now trying 1000 iterations of brent's method now trying william's (p+1) method phase 1 - trying all primes less than 10000 phase 2 - trying last prime less than 1000000 now trying pollard's (p-1) method phase 1 - trying all primes less than 100000 phase 2 - trying last prime less than 5000000 now trying lenstra's method using 10 curves curve 1 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 PRIME FACTOR 82855971825577 PRIME FACTOR 169233693573475517436547188037
This page was last updated on: November 9, 2009.