> For the complete documentation index, see [llms.txt](https://davidjosearaujo.gitbook.io/notes-mcs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://davidjosearaujo.gitbook.io/notes-mcs/applied-cryptography/rsa-and-related-subjects/fast-modular-multiplication.md).

# Fast Modular Multiplication

A modular multiplication requires a remainder operation, which is a slow operation if the modulus is a general integer. For example, contemporary processors can multiply two 64-bit integers, producing a 128-bit result, with a latency of 3 or 4 clock cycles. But, dividing a 128-bit integer by a 64-bit integer, producing a 64-bit quotient and a 64-bit remainder, is considerably slower (tens of clock cycles).

If the modulus is a power of two, say $$2^n$$,the remainder operation is very fast; the remainder is just the last *n* bits of the number being remaindered. In 1985, Peter Montgomery came up with a beautiful way to explore this to efficiently perform general remaindering operations without performing an expensive division.

## The Greatest Common Divisor

Let $$p\_k$$ be the $$k$$-th prime number, so that $$p\_1=2, p\_2=3, p\_3=5$$, and so on,

Each positive integer can be factored into prime factors in a unique way (this is the fundamental theorem of arithmetic).

Let $$a = \Pi^\infty\_{k=1}p^{a\_k}\_k$$, where $$a\_k$$ is the number of times $$p\_k$$ divides $$a$$. Since $$a$$ is a finite number, almost all of the $$a\_k$$ values will be zero.

Likewise of $$b$$, let $$b = \Pi^\infty\_{k=1}p^{b\_k}\_k$$.

Then $$gcd(a,b) =\Pi^\infty\_{k=1}p^{min(a\_k,b\_k)}*k$$ and $$lcm(a,b) =\Pi^\infty*{k=1}p^{max(a\_k,b\_k)}\_k$$

If $$gcd(a,b) = 1$$ then $$a$$ and $$b$$ are said to be relatively prime (or coprime).

**The greatest common division can be generalized to a polynomial with integer coefficients!**

### Algorithm

Assume that $$a \ge 0$$ and that $$b \ge 0$$. Then:

* $$gcd(a,b) = gcd(b,a)$$, and so $$gcd(a,b) = gcd(max(a,b), min(a,b))$$. Thus, by exchanging $$a$$ with $$b$$ if necessary, we may assume that $$a \ge b$$.
* as any positive integer divides 0 we have $$gcd(a,0) = a$$ for $$a \gt 0$$. The mathematicians say that $$gcd(0,0) = 0$$, and so we can say that $$gcd(a,0) = a$$ as long as $$a \ge 0$$.
* If $$a \ge b$$ the $$gcd(a,b) = gcd(a-b,b)$$. We can keep subtracting $$b$$ from (the updated) $$a$$ until it becomes smaller than $$b$$, and so $$gcd(a,b) = gcd(a mod b, b) = gcd(b, a mod b)$$.

These observations give rise to the following so-called Euclid's algorithm (coded in `C`, but it can easily be translated to another programming language):

```
long gcd(long a, long b)
{
    while(b != 0) { long c = a % b; a = b; b = c; } return a;
}
```

The GNU MP library has a function, `mpz_gcd`, for this; `pari-gp` does this with the gcd function.