TABLE OF CONTENTS When we think of long-hand arithmetic such as addition or multiplication, we rarely consider the fact that we instinctively raise or lower the precision of the numbers we are dealing with. For example, in decimal we almost immediately can reason that 7 times 6 is 42. However, 42 has two digits of precision as opposed to the one digit we started with. Further multiplications of say 3 result in a larger precision result 126. In these few examples we have multiple precisions for the numbers we are working with. Despite the various levels of precision, a single subset [1] of algorithms can be designed to accommodate them.
By way of comparison, a fixed or single precision operation would lose precision on various operations. For example, in the decimal system with fixed precision 6 7 = 2.
Essentially, at the heart of computer-based multiple precision arithmetic are the same long-hand algorithms taught in schools to manually add, subtract, multiply, and divide.
The most prevalent need for multiple precision arithmetic, often referred to as "bignum" math, is within the implementation of public key cryptography algorithms. Algorithms such as RSA [10] and Diffie-Hellman [11] require integers of significant magnitude to resist known cryptanalytic attacks. For example, at the time of this writing a typical RSA modulus would be at least greater than 10 309. However, modern programming languages such as ISO C [17]...
