bigint - large integer package

This library lets you do math on arbitrarily large integers. It's reasonably fast - compared with the multi-precision routines in the "bc" calculator program, these routines are from two to ten times faster, except for division which is maybe half as fast. Compared with a more finely-tuned package such as gmp, it's probably somewhat slower. Top speed isn't actually the point of this package, though. The interesting aspects are:

API

The routines use a unique calling convention designed for clarity of expression. See the man page for details.

Division

The multi-precision division algorithm used here is apparently a new invention. It's not real fast, but it's very simple.

License

As with all ACME Labs software this package uses a Berkeley-style license, which lets you do more than the restrictive Gnu license on the gmp package.

In addition to the library routines, the package includes a couple of sample applications.

bic - simple arbitrary-precision calculator

A simple calculator program that handles arbitrarily-large numbers. It's similar to the standard "bc" calculator, but can handle larger numbers, goes somewhat faster, and has some more special functions. However unlike "bc" it does not handle fractional numbers, only integers. It also does not implement bc's booleans, bit operations, functions, etc.

bic implements the following basic operators, with the usual precedences:

+ - * / % ^ ! ()

sqrt( x )

square root

gcd( x, y )

greatest common divisor

lcm( x, y )

least common multiple

modpow( x, y, z )

modular exponentiation - equivalent to ( x ^ y ) % z, but much faster

modinv( x, y )

modular inverse

random( x )

random number in [0..x)

bits( x )

number of bits in x

jacobi( x, y )

the Jacobi symbol

isprime( x, y )

check whether x is a prime number, to certainty y

genprime( x, y )

generate a probable prime number x bits long, with certainty y

You can try out the bic calculator with this form interface.

Note that bic's operations are enough to perform RSA encryption. Here's an example.

First, decide how many bits long you want your keys to be. Let's say 500. Generate two prime numbers half that long (takes a couple seconds each):

p = genprime(250,4)
q = genprime(250,4)

n = p * q
o = (p-1) * (q-1)

e = random(o)

d = modinv(e,o)

Now you have your public and private keys. Pick a message to encrypt, up to 500 bits long:

m = 12345678901234567890123456789012345678901234567890

c = modpow(m,e,n)

modpow(c,d,n)
12345678901234567890123456789012345678901234567890

bi_factor - prime-factor large numbers

The program will compute the prime factors of each number you give it as an argument. In addition to simple integers, you can also specify a range of integers as "int-int", or you can use up to 3 trailing wildcards. Here are some examples:

% bi_factor 2147483647 4294967295 8589934591 17179869183
2147483647 = 2147483647
4294967295 = 3 5 17 257 65537
8589934591 = 7 23 89 599479
17179869183 = 3 43691 131071
% bi_factor 1099511627774-1099511627778
1099511627774 = 2 7 79 8191 121369
1099511627775 = 3 5^2 11 17 31 41 61681
1099511627776 = 2^40
1099511627777 = 257 4278255361
1099511627778 = 2 3^2 2731 22366891
% bi_factor 123456789012345.
1234567890123450 = 2 3 5^2 283 3851 7552031
1234567890123451 = 13 67 823 3733 461359
1234567890123452 = 2^2 7243931 42606973
1234567890123453 = 3^4 479 31819580147
1234567890123454 = 2 971 175463 3623099
1234567890123455 = 5 246913578024691
1234567890123456 = 2^6 3 7^2 301319 435503
1234567890123457 = 6101 18401 10996957
1234567890123458 = 2 11 349 160792900511
1234567890123459 = 3 233 1168477 1511533

Note however that while the program can handle arbitrarily large numbers, the factoring algorithm is currently the slowest one around, trial division, so there's not much point in trying to factor numbers larger than 16 digits or so (which is about 53 bits).

You can try out the bi_factor program with this form interface.