# Montgomery modular multiplication

The computation of

is much slower than usual multiplication, since it requires a division to know how many times has to be subtracted from the product.Montgomery modular multiplication is a way to do this computation faster. The trick is to move the computations to the Montgomery space which contains the integers smaller than

for some positive integer We move the element to the Montgomery space by multiplying it byLet’s say we need to compute

We compute

then we need to divide it by and finally we need to subtract if the result is bigger than (we know that the result is smaller than because ).Well, this is more complicated than simply computing

and then subtracting if the result is bigger than However, it is not much more complicated if we do it the right way. Instead of computing simply as integers and in the last step computing modulo (subtracting if necessary), we can much more efficiently compute:Let’s see how.

## Efficient division by R modulo p

Note that

That means

For computers, dividing by

means almost no work; it’s just a shift operation. Given that is divisible by division by means shifting by positions:Of course,

might not be divisible by But in we have some liberty to make an arbitrary divisible byWe just need to find

such that is divisible byComputing

in means computing the inverse of in (which is the same as the inverse of in ) – let’s denote this inverse by – and then computingFor any

it holds:But once we have

such that is divisible by we can compute simply in integers as So we can compute very efficiently simply by shifting by positions:We will see in the example section how to compute

(and why is smaller than which makes it easy to make it smaller than ).## Multiplication

As we saw above, addition by moving to the Montgomery space and back is not much more expensive than without moving it there and back, but the real reason we are moving to the Montgomery space is multiplication.

The computation of

is not nearly as simple as the computation of where in the worst-case scenario we need to do an additional subtraction of This is why we move to the Montgomery space. We get such that:We compute

and reduce it back to the Montgomery space by dividing it by Note that:So by dividing

by we get:So we have a Montgomery representation of

To compute the final value we again use the efficient division byNote that this pays off when we have multiple operations. We move the elements to the Montgomery space, execute all the operations in the Montgomery space, and as the last step move the elements back from the Montgomery space.

## Example

For demonstration purposes, let’s have:

The division of

by would go as follows.First, we compute:

Note that for some

We then compute:

Let’s observe the expression above modulo

That means we can divide

So we found

We can compute

Because

(this is our Montgomery space) andIf

then we computeFinaly, we have

such that: