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

 - [Peter L. Montgomery][1]; [Modular multiplication without trial division][2] ,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}$$

  [1]: https://en.wikipedia.org/wiki/Peter_Montgomery_(mathematician)
  [2]: https://doi.org/10.1090/S0025-5718-1985-0777282-X