MadSci Network: Computer Science |

Posted By:

Area of science:

ID:

As you have noticed, personal computers are built to perform
arithmetic operations in two regimes: *exact* arithmetic using
integers of limited size, and *approximate* arithmetic using
not-necessarily-integer values over a much larger range of magnitudes.
The latter is called "floating-point arithmetic," and although it
may offer many significant digits of accuracy, the fact that it is
not exact makes it generally useless for cryptographic applications,
to which the old English saying "a miss is as good as a mile" applies.

Consequently, people who need to perform exact arithmetic
on large integer values must find ways to represent such values
using the hardware available. A common approach is to use a
long succession of single-byte values, preceded by an ordinary
integer telling how many bytes follow. Each of the single-byte
values holds an integer in the range 0 to 255, and the values
are regarded as digits in a base-256 representation of the large
integer. In other words, the value of the large integer is defined
to be the first byte, plus 256 times the second byte, plus
256^{2} times the third byte, continuing through all
the bytes.

To make use of these large integers, one needs a library of functions for adding them, subtracting them, multiplying them, dividing them, comparing them, and more. Such libraries are sprinkled across the World Wide Web, and can be found by searching on terms like "big integer", "large integer", "bigint", "bignum", and "extended precision integer". Writing a bigint multiplication function takes you back to elementary school, because the algorithms we were taught at age 10 for multiplying base-10 representations of integers turn out to be easily extended to base-256 integers.

Most Unix-family computers come with utility programs named bc and dc that perform extended-precision arithmetic. According to a web search I just performed, you can download an interactive interpreter for big integer arithmetic and multi-precision floating point arithmetic, suitable for use on Unix, Linux, Windows 95/98/NT, MSDOS, and Atari, called Aribas. A Java class for big-integer arithmetic is available at http://www.minmet.uq.oz.au/java/api/java.math.BigInteger.html. Finally, if you're feeling courageous and want to see big-integer C code employed in a cryptographic application, go to http://web.mit.edu/network/pgp.html download the PGP source code, and examine the mpilib sources.

Try the links in the MadSci Library for more information on Computer Science.

MadSci Network, webadmin@www.madsci.org

© 1995-1999. All rights reserved.