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.

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):

Compute their product, and the product of one less than the primes:`p = genprime(250,4) q = genprime(250,4)`

Pick a public key - a random number less than o:`n = p * q o = (p-1) * (q-1)`

Compute the corresponding private key:`e = random(o)`

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

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

Encrypt it with your public key (this takes a few seconds):`m = 12345678901234567890123456789012345678901234567890`

Decrypt it with your private key (also takes a few seconds):`c = modpow(m,e,n)`

That's all there is to it!`modpow(c,d,n) 12345678901234567890123456789012345678901234567890`

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.

Back to ACME Labs Software.

Back to ACME Labs.