Library mont_mul_prg

The Montgomery multiplication is a modular multiplication. The advantage of the Montgomery multiplication is that it does not require multi-precision division, but used less-expensive shifts instead. The price to pay is a parasite multiplicative factor whose elimination requires two passes.

The implementation of the Montgomery multiplication we deal with is the so-called ``Finely Integrated Operand Scanning'' (FIOS) variant . Intuitively, it resembles the classical algorithm for multi-precision multiplication: it has two nested loops, the inner-loop incrementally computes partial products (modulo) that are successively added by the outer-loop. These partial products are computed in such a way that the least significant word is always zero, thus guaranteeing that the final result will fit in k+1 words of storage (where k is the length of multi-precision integers). For this to be possible, the Montgomery multiplication requires the pre-computation of the modular inverse of the least significant work of the modulus.

The SmartMIPS architecture is well-suited to the implementation of the FIOS variant of the Montgomery multiplication because the addition performed in the inner-loop (that adds two products of 32-bits integers) fits in the integer multiplier (of size greater than 72 bits).

Let A by the value of the multiplier before entering the inner-loop and A % n be the remainder of the division of A by 2^n. The Montgomery multiplication computes quot = ((A%32) [.*] alpha)%32 and adds quot [.*] M0 to the multiplier. The lemma below captures the fact that the resulting multiplier is a multiple of 2^32, and thus the least significant word of the partial product is always zero: