# How to compute $$R^2\mod N$$?

## Using Montgomery modular multiplication

Posted on May 30, 2020 -

In order to use Montgomery modular multiplication, we need to know $$R^2\mod N$$. If we already have Montgomery multiplier in hand, can we avoid brute-force calculation?

First, a brief review of the Montgomery modular multiplication:

Let us take 256 bits as an example. Let $$N$$ be the modulus, and take $$R = 2^{256}$$, and Montgomery modular multiplication can be defined by $$M(A, B) = A\times B / R\mod N$$.

How to use Montgomery modular multiplication to calculate R$$R^2\mod N$$? Here's an example.

Let $$m = 2^{256} - 1\mod N, m_1 = m + m + 2\mod N = 2\times 2^{256} \mod N$$, then

$$m_2 = M(m_1, m_1) = 2^{2} \times 2^{256} \mod N$$

$$m_4 = M(m_2, m_2) = 2^{4} \times 2^{256} \mod N$$

$$m_8 = M(m_4, m_4) = 2^{8} \times 2^{256} \mod N$$

$$\dots$$

$$m_{256} = M(m_{128}, m_{128}) = 2^{256} \times 2^{256} \mod N = R^2 \mod N$$

As a result, in order to calculate the number $$R^2 \mod N$$, we need to:

1. calculate the modular addition of $$2^n-1$$ and $$1$$, and the result is noted as $$a$$.
2. calculate the modular addition of $$a+a$$, and the result is noted as $$m_1$$.
3. Calculate the Montgomery modular multiplication of $$m_i$$ and $$m_i$$, and the result is noted as $$m_{2i}$$. Repeat step 3 for $$\log_2n$$ times.

The total number of operations is: 2 additions and $$\log_2n$$ multiplications.