First lets remind ourselves of the definition of modular arithmetic.

Modular arithmetic

Within a computers architecture as numbers are stored in binary calculating mod $2^k$ is simple as taking the $k$ least significant bits. Therefore it is quite cheap. However, when the value is not $2^k$ it can get harder.

Exponent problem

Statement

This is the problem we want to solve in the next step. We would like an algorithm that is linear in $n$ which would be the input size. Note that $x$, $y$ and $N$ are all bounded by $2^n$ so if this appears in our bound we will be exponential.

It is quite easy to calculate $x^{2k}$ (mod $N$) as you recursively calculate $(x^{2i})^2$ (mod $N$). Using this idea we get a first attempt at solving the above problem.

Modular exponent algorithm

Multiplicative inverse problem

This may not exist if $N$ is not prime.

Modular multiplicative inverse existence

Though knowing an inverse exists isn’t helpful algorithmically.

Statement

Let’s first look at a helpful rule for finding this.

Euclid’s rule

We can use this rule to calculate greatest common divisors.

Euclidean algorithm

Moreover we can extend this to calculate the inverse.

Extended Euclidean algorithm

Example

To compute $7^{-1}$ mod $360$ we run the Extended Euclidean algorithm on $7$ and $360$.

First calculate the $x$, $y$ and $c$ columns going downwards. Where $x_i = y_i \cdot c_i + y_{i+1}$ with $x_{i+1} = y_i$.

Second calculate $a_i$ and $b_i$ starting form the bottom where $a_{i-1} = b_i$ and $b_{i-1} = a_{i} - c_{i-1} \cdot b_i$. Note $d = min_i \ x_i$.

Then as $1 = -2 \cdot 360 + 103 \cdot 7$ we have that $103 = 7^{-1}$ mod $360$.