bigint - large integer package

Fetch the software.

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:


+ - * / % ^ ! ()
    

And the following special functions:

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)
    

Compute their product, and the product of one less than the primes:


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

Pick a public key - a random number less than o:


e = random(o)
    

Compute the corresponding private key:


d = modinv(e,o)
    

If this step fails (due to e not being relatively prime to o), pick another e. It may take a few tries.

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


m = 12345678901234567890123456789012345678901234567890
    

Encrypt it with your public key (this takes a few seconds):


c = modpow(m,e,n)
    

Decrypt it with your private key (also takes a few seconds):


modpow(c,d,n)
12345678901234567890123456789012345678901234567890
    

That's all there is to it!


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.


ACME Labs / Software / bigint
email