How does Montgomery reduction work?

Question

I want to reduce a multi-precision integer $x$ modulo a prime $p$, very fast. Performing the traditional Euclidean division for only calculating the modulo, is inefficient and modular reduction is at the heart of many Cryptographic primitives like Elliptic Curve Cryptography. There are other methods to perform the aforementioned task like Barret reduction, etc, but I would like to learn about Montgomery reduction and its peculiarities first, because of its practical significance. Algorithm:

     Input : Integer x, n, k 
     Output : (2^(-k) * x) mod n
    1. for t from 1 to k do
        1.1 if x is odd then
            1.1.1     x <- x+n
        1.2 x <- x/2
    2 Return x

There are restrictions on $x$ like, $0$ <= $x$ < $n^2$, and also, $n$ should be odd. The book from which, I borrowed the above algorithm from , states two facts:

Fact 1 : Adding n to x does not change the residue, since in effect it adds one to the quotient ⌊x/n⌋. Another way to explain this is that n is (or multiples of n are) congruent to zero modulo n. Adding zero will not change the value of the residue.

Fact 2: If $x$ is even, then performing a division by two in $Z$ is congruent to $x · 2^{−1} \mod n$ . Actually, this is an application of the fact that if x is evenly divisible by any $k$ ∈ $Z$, then division in Z will be congruent to multiplication by $k^{−1}$ modulo $n$ .

I don't understand the meaning behind Fact 2. In reality, I'm having trouble in comprehending how the author transcends from regular arithmetic to modular arithmetic mod n ? Why is it that division of $x$ by two in $Z$ (integers) is congruent to multiplication by $2^{-1}$ in modulo $n$. After all $2^{-1}\mod n$ can be easily calculated by the extended euclidean algorithm: Since, $n = 2*q + r$. Since $n$ is odd, $r$ should be $1$. Therefore on transposing, we get: $n - 2*q = 1$. If we take this preceding equation modulo $n$, we get $-q$ as the multiplicative inverse of $2$ w.r.t mod n.

It would be highly appreciated, if I could get a good explanation of how Montgomery reduction works, in the first place. Why do we keep adding $n$ to $x$ , if $x$ is odd?

I am missing some very great clarity in my understanding! What are the solid principles behind Montgomery multiplication with reduction ? Since, I come from mostly programming background, I seem to be lacking some mathematical knowledge in this context.

Every help will be greatly appreciated!

Answer 1

In 1985, Montgomery introduced a new clever way to represent the numbers $\mathbb{Z}/n \mathbb{Z}$ such that arithmetic, especially the modular multiplications become easier.

• Peter L. Montgomery; Modular multiplication without trial division ,1985

We need the modulus $n$ we are working and an integer $r$ such that $\gcd(r,n) =1$ and $r>n$

Definition: The Montgomery representation of $x \in [0,n-1]$ is $\bar{x} = (xr) \bmod n$

Definition: The Montgomery reduction of $u \in [0,rn-1]$ is $Redc(u) = (ur^{-1}) \bmod n$. This is also called $n$-residue with respect to $r$. Indeed, one can show that this set $$\{i\cdot r \bmod n | 0 \leq i \leq n\}$$ is a complete residue system.

In Cryptography, we usually work with prime modulus therefore we can chose $r = 2^k$. In this case the $\gcd(r,n) = \gcd(2^k,n) = 1$ is satisfied.

Fact 1 :

Since we are working modulo $n$, this is an elementary result.

Fact 2: If $x$ is even, then performing a division by two in $\mathbb{Z}$ is congruent to $x\cdot 2^{−1} \bmod n$. Actually, this is an application of the fact that if $x$ is evenly divisible by any $k \in \mathbb{Z}$, then division in $\mathbb{Z}$ will be congruent to multiplication by $k^{−1} \bmod n$.

What they try to say is

• Let $k$ divides $x$ then $u \cdot k = x$ take the modulus $n$ on both sides. $$u \cdot k = x \bmod n$$ Since $n$ is prime than $k^{-1}$ exist in modulo $n$ and that can be found with the Extended Euclidean Algorithm. For Montgomery this is required only once for $r$. Now we have;

$$u \cdot k \cdot k^{-1} = x \cdot k^{-1} \bmod n$$

$$u = x \cdot k^{-1} \bmod n$$

1.2 x <- x/2

When the $r = 2^k$ this is usually performed by shift operations. This is a trick of the Montgomery. The trial division is transferred into shifts.

x = x >> 2

What are the solid principles behind Montgomery multiplication with reduction?

Montgomery Reduction This is the Wikipedia version.

input: Integers r and n with gcd(r, n) = 1,
       Integer n′ in [0, r − 1] such that nn′ ≡ −1 mod r,
       Integer T in the range [0, rn − 1]
output: Integer s in the range [0, n − 1] such that s ≡ Tr^−1 mod n

m = ((T mod r)n′) mod r
t = (T + mn) / r
if t ≥ n then
    return t − n
else
    return t

Now, the advantage is clear. Since $r= 2^{k}$ the division and $\bmod$ operations are cheap by shifting or masking.

The $n'$ is defined as $rr^{-1} -n n' =1$

The correctness can be seen by

• observe that if $m = (( T \bmod r )n^{'}) \bmod r$ then $T + mn$ is divisible by $r$.

$$T + mn \equiv T + (((T \bmod r)n') \bmod r)n \equiv T + T n' n \equiv T - T \equiv 0 \pmod{R}$$ There for the $t$ is integer, not a floating point.

The output then is either $y$ or $t-n$ ( remember the fact 1). Now let see why the output is $Tr^{-1}$. We again use what we know

$$t \equiv ( T + mn )r^{-1} \equiv Tr^{-1} + (mr^{-1})n \equiv Tr^{-1} \pmod{n)}$$

Therefore the output has the correct residue as we wanted.

Why the substruction? We need to keep track of the $t$'s size.

• $m \in [0,r-1]$
• $T+mn$ then lies between $0$ and $(rn-1) + (r-1)n < 2rn$. Since the divived by $r$ then $0 \leq t \leq 2n-1$. A single substraction can reduce the $t$ into the desired range.

Montgomery Product

We are going to define a function that is going to be very powerful. Remember $\bar{a} = ar \bmod n$

• $MonPro(\bar{a},\bar{b},r,n)$

  //outputs $t = MonPro(\bar{a},\bar{b},r,n) = \bar{a}\bar{b}r^{-1} \pmod{n}$

  • $ T = \bar{a}\bar{b}$
  • $m = T n' \bmod r$
  • $t = (T+mn)/r$
  • if $t \geq n$ $\text{return}(t-n)$
  • $\text{return}(t)$

Let us simplify the $MonPro(\bar{a},\bar{b},r,n)$ to $MonPro(\bar{a},\bar{b})$ since we keep them constant and $r^{}$ can be calculated as constant before the operations.

• What will happen if we call : $MonPro(\bar{a},1)$?

$$MonPro(\bar{a},1) = (a r) \cdot 1 \cdot r^{-1} = a \pmod{n}$$

• What will happen if we call : $MonPro(\bar{a},b)$?

$$MonPro(\bar{a},b) = (a r) \cdot b \cdot r^{-1} = a \cdot b\pmod{n}$$

• What will happen if we call : $MonPro(a,r)$?

$$MonPro(a,1) = a \cdot 1 \cdot r^{-1} = a r^{-1} \pmod{n}$$