Montgomery-Multiplication
蒙哥馬利還原 - R 上的條件
在蒙哥馬利約簡中，我們需要計算 $ z = x y \text{ mod } N $ 和蒙哥馬利減少 $ x $ 是 $ xR^{-1} $ .
- 為什麼要選擇 $ R $ 是 $ 2^l $ 在哪裡 $ l $ 是長度 $ N $ 到基地 $ 2 $ ?
- 為什麼我們不能有更大的 $ R $ ?
這是一個與math.stackexchange的交叉問題。
首先，蒙哥馬利的歸約算法要求 $ \operatorname{GCD}(n,R)=1 $ . 滿足這個要求 $ n $ 很奇怪。
這 $ R $ 被選為 $ 2^l $ 在哪裡 $ 2^{l-1} \leq n < 2^{l} $ .
為了 $ x < n $ 這 $ n $ - 殘留物 $ R $ 定義為；
$$ x’ = x \cdot r \bmod n $$比集合
$$ {i \cdot R \bmod n;|; 0 \leq i \leq n-1 } $$是一個完整的餘數係統，即它包含了之間的所有數 $ 0 $ 和 $ n-1 $ .
的選擇 $ R $ 是最小的界限。
- 為什麼要選擇 $ R $ 是 $ 2^l $ 在哪裡 $ l $ 是長度 $ N $ 到基地 $ 2 $ ?
Montgomery Reduction 將任意除法轉換為移位操作。所以 $ 2^l $ 是電腦的好選擇，我們要換檔 $ l $ 位。
- 為什麼我們不能有更大的 $ R $ ?
它不會有效，因為您將有更多不必要的轉變，因為更大 $ R $ .
**注意：**如果 $ R<n $ 比這行不通。