Montgomery-Multiplication
蒙哥馬利乘法的有效設置
Montgomery 描述了一種計算模乘的有效方法。這通過使用一個特殊的常數來工作 $ R $ 並假設輸入 $ a $ 和 $ b $ 已製成特殊表示（殘基 $ aR\mod N $ 和 $ bR\mod N $ ) 並產生價值 $ abR^{-1}\mod N $ . 因此，要進行計算，需要值 $ ab $ 也處於特殊表示中，這需要與常數進行額外的（蒙哥馬利）乘法 $ R^2\mod N $ .
這對於計算模數較大的模冪特別有用 $ N $ 和一個很大的指數，比如在 RSA 中。
每一步，例如計算特殊表示 $ a $ 和 $ b $ 是昂貴的，因此計算 $ R^2\mod N $ （請注意，它必須計算一次，但仍然很昂貴）。
有哪些不同的計算方法 $ R^2 \mod N $ 有效率嗎？
通常的方法是計算 $ 2^k R \bmod N $ 對於一個小的除數 $ k $ 的 $ l $ 在哪裡 $ R = 2^l $ 並在平方乘法算法中使用蒙哥馬利乘法。這確實需要除法，但作為 $ R $ 通常選擇比 $ N $ ，除法不必優化太多。
但是您還應該考慮這樣一個事實，即在某些情況下（例如 RSA 密鑰生成），您也可以在不知道的情況下進行 $ R^2 \bmod N $ . 您既不需要蒙哥馬利轉換費馬或米勒拉賓檢驗的隨機基數，也不需要使用費馬小定理反轉的數字（在第二種情況下，只需蒙哥馬利乘以 $ 1 $ 然後）。