Re: How does one calculate large numbers on a computer?

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² 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.