The Montgomery in 1985 introduced a new clever way to represent the numbers $\mathbb{Z}/n \mathbb{Z}$ such that arithmetic, especially the multiplications become easier.
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 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 trick of the Montgomery. The trial division is transferred into shifs.
x = x >> 2
What are the solid principles behind Montgomery multiplication with reduction ?
Montgomery Reduction This is 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.