为了使用Montgomery模乘，我们需要知道 \(R^2\mod N\)，如果手里已经有了Montgomery模乘，能避免硬算吗？
答案是能。
首先简要回顾一下Montgomery模乘：
我们以256比特为例，记 \(N\) 为需要取模的数，取 \(R=2^{256}\)，则Montgomery模乘为 \(M(A, B) = A \times B / R \mod N\)。
那么如何利用Montgomery模乘来计算 \(R^2\mod N\)呢？来看个例子：
令 \(m = 2^{256} - 1 \mod N, m_1 = m + m + 2 \mod N = 2 \times 2^{256} \mod N\)，则有
\(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\)
所以，为了计算 \(n\)比特（假设 \(n\)是2的幂）的数 \(N\)对应的 \(R^2 \mod N\)，我们可以这样做：
- 计算 \(2^n-1\)与 \(1\)的模加，记结果为 \(a\)
- 计算 \(a+a\)的模加，记结果为 \(m_1\)
- 计算 \(m_i\)与\(m_i\)的Montgomery模乘，记结果为 \(m_{2i}\)，重复 \(\log_2n\)次
总的操作次数是：2次加法和 \(\log_2n\)次乘法。