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\)
\(\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:
- calculate the modular addition of \(2^n-1\) and \(1\), and the result is noted as \(a\).
- calculate the modular addition of \(a+a\), and the result is noted as \(m_1\).
- 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.