Computer Security and Cryptography

13.11 MULTIPRECISION ARITHMETIC

The 43rd Mersenne prime contains 9,152,052 digits, not the kind of number we are used to writing out, much less manipulating. Although such numbers usually do not arise in day-to-day computations, some public-key cryptosystems require numbers with several hundred digits. Floating-point computations arising in navigational calculation also require great precision. The basic modular operations addition, multiplication, and division on numbers with a very large number of digits use a pencil and paper, a technique learned in elementary school.

Each n-digit base-b number is represented as a string of characters x:x_n−1, x_n−2 … x₁x₀ where x_i is a base-b digit. Addition (multiplication and divison) is performed using digit-by-digit operations. For example, addition

TABLE 13.15 Multiprecision Parameters and Operations

is carried out in a single DO-loop.

Subtraction, multiplication, and division are implemented similarly. Division is the most tedious, producing a quotient and a remainder. The Montgomery reduction is used to make the computation of a^m (modulo N) more efficient.

Multiprecision modular arithmetic is needed in cryptography, for example, to implement RSA encipherment. Modular operations combine an addition/multiplication and division step. The parameters ...