5.1 The Multipliers

For most number theoretic problems, including certain public key cryptographic algorithms, the "multipliers" form the most important subset of algorithms of any multiple precision integer package. The set of multiplier algorithms include integer multiplication, squaring, and modular reduction, where in each of the algorithms single precision multiplication is the dominant operation performed. This chapter discusses integer multiplication and squaring, leaving modular reductions for the subsequent chapter.

The importance of the multiplier algorithms is for the most part driven by the fact that certain popular public key algorithms are based on modular exponentiation; that is, computing d ? a ^b (mod c) for some arbitrary choice of a, b, c, and d. During a modular exponentiation the majority ^[1] of the processor time is spent performing single precision multiplications.

For centuries, general-purpose multiplication has required a lengthy O( n ²) process, whereby each digit of one multiplicand has to be multiplied against every digit of the other multiplicand. Traditional long-hand multiplication is based on this process; while the techniques can differ, the overall algorithm used is essentially the same. Only "recently" have faster algorithms been studied. First Karatsuba multiplication was discovered in 1962. This algorithm can multiply two numbers with considerably fewer single precision multiplications when compared to the long-hand approach. This technique led to the discovery of polynomial basis algorithms [19] and subsequently Fourier Transform based solutions.