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?

The answer is yes.

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


\(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.