## My Software Page

This page describes some software that I have written, (and some that I didn’t 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.

### fact.exe

fact.exe is a calculator-type program that runs in a command window on 32-bit or 64-bit Windows. 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:

e=99,z=1009
d=e\z
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

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.

### factor.exe

This program was written by Shamus Software (not sure if they still have a website) and will successfully factor any number up to 80 digits, using several different factoring algorithms. It will make an attempt, sometimes successfully, to factor larger numbers, up to its limit of about 135 digits.

Shamus has placed factor.exe into the public domain, though I don’t know if it is still available for download. I downloaded the source code from their website (many years ago), made a few small changes, and compiled it for Windows (32-bit or 64-bit). Updated on October 7, 1999.

A version of factor.exe, which I call factor2.exe, works with larger numbers, up to about 280 digits.

Another version of factor.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.

### Examples

Here is an example of fact or fac.
```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
>
```

Here are some examples of factor.

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     1231026625769
```
Or 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     1728135292692949031248613
```
And 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
```

Go to my math index page.