Modular multiplication

Problem: , calculate

Montgomery multiplication

Aim is to add a multiple of to such that, it becomes divisible by . Choose different divisor such that,

i.e. is negative inverse of . Generally, R is chosen to be power of 2, like , so that division by R is just right bit shift by .

Note: . Let’s understand how works:

Cost: 3 big-int mults. integer multiplication.

Prove: and :

Multi precision, radix

Choose: , and

  1. Initialize
  2. update t every loop , such that
  3. divide R:


We’ll prove this using induction. So,

Thus, divides . similarly, let’s formulate :

understand above from Montgomery modular multiplication

Instead of updating every loop, we’ll split and update and shift by a word after each loop, which is essentially dividing by . Explaining CIOS algorithm from