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. 

 - [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 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

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