爲了使用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\)次乘法。