notes - December 7, 2023

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 by

Let’s say we need to compute

We move the computation to the Montgomery space:

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

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

Of course,

might not be divisible by
But in
we have some liberty to make an arbitrary
divisible by

We just need to find

such that
is divisible by


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

For 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

We will see in the example section how to compute

(and why
is smaller than
which makes it easy to make it smaller than


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

we get:

So we have a Montgomery representation of

To compute the final value
we again use the efficient division by

Note 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.


For demonstration purposes, let’s have:

The division of

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

using the shift operation.

So we found

that we were looking for in the Efficient division section above.

We can compute


(this is our Montgomery space) and
we have


then we compute

Finaly, we have

such that:

Boogie Math Newsletter

Some characters on this website might be partially or entirely fictional. You have been warned, my friend!

© 2023 Boogie Math, all rights reserved Follow us: Twitter