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

We just need to find

such that
is divisible by

Computing

in
means computing the inverse of
in
(which is the same as the inverse of
in
) – 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
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 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.

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

by
using the shift operation.

So we found

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

We can compute

Because

(this is our Montgomery space) and
we have

If

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