哪個最快？Karatsuba 或蒙哥馬利乘法？
Karatsuba和蒙哥馬利乘法算法之間是否有任何復雜性分析？似乎 Karatsuba 更通用，因為它不是模數調整的，而蒙哥馬利是模數調整的。是否也存在使用 Karasuba 和 Montogomery 的混合模型？
總結：與經典算法相比，Montgomery 的目標只是適度（如果有的話）加速；由於其他原因，它很受歡迎。Karatsuba 允許對非常大的參數進行大幅加速，但在加密應用程序中通常無法達到它變得有利的門檻值。這些技術可以一起使用。
蒙哥馬利算術用於模乘和取冪，這是密碼學中的常見操作（RSA，一些橢圓曲線密碼系統）。以一些預計算和後計算為代價（當指數大到足以保密時，成本幾乎可以忽略不計），它簡化了模組化減少步驟，特別是有兩個好處：
- 它避免了對商的可能錯誤估計，這在經典算法中會導致一種特殊情況；從側通道洩漏（例如定時攻擊）的角度來看，這是有益的；並且通過它提供的安心（經典商估計及其特殊情況很難正確和完全測試）。
- 商估計的蒙哥馬利等價物是基於要減少的值的低位（而不是高位）執行的，這簡化了在臨時結果的同一掃描中交錯的乘法和模減少的實現（即交錯反過來，與天真地計算一個完整的乘積然後減少它相比，該技術反過來將操縱的數字的寬度限制在模數的大小，並減少了記憶體訪問的次數）。
然而，與使用經典算法的相當好的實現相比，蒙哥馬利算法的成本幾乎沒有變化，同時考慮了基本的乘法和記憶體訪問。模冪與 $ n $ -位數，包括成本的指數餘數 $ \mathcal O(n^3) $ . 更準確地說，對於蒙哥馬利算法和經典算法，使用 $ w $ 位字，交錯乘法和減少，以及隨機指數的基本掃描： $ \approx{3\over w^2}n^3 $ 乘以和累加雙倍寬度的結果，和 $ \approx{6\over w^2}n^3 $ 記憶體訪問（ $ {3\over4} $ 讀， $ {1\over4} $ 寫）。
Karatsuba 乘法是一種用於（非模）乘法的分而治之算法，用於 $ n $ 位整數降低了成本 $ \mathcal O(n^2) $ 對於經典乘法 $ \mathcal O(n^{\log_2 3}) $ ， 那是 $ \mathcal O(n^{1.58\dots}) $ .
應用於模冪運算 $ n $ - 位數，包括指數，成本從 $ \mathcal O(n^3) $ 到 $ \mathcal O(n^{1+\log_2 3}) $ ， 那是 $ \mathcal O(n^{2.58\dots}) $ . 在模減少期間獲得 Karatsuba 乘法的好處的幾種方法之一是將模的（非模）逆預先計算為略大於 $ n $ 位，可以按成本完成 $ \mathcal O(n^2) $ （因此可以忽略不計 $ \mathcal O $ 關心）與經典算法。
Karatsuba 乘法僅在超過某些門檻值時才有益 $ n $ . 該門檻值因很多事情而異。在針對低功耗優化的硬體乘法器中，Karatsuba 付出了適度的代價 $ n $ . 在GNU MP Bignum Library中，非模乘法的預設值曾經
KARATSUBA_THRESHOLD高達 32（即 Karatsuba 用於 $ n\ge32w $ 通常與 $ w=32 $ ); 模冪運算的最佳門檻值往往顯著更高。在現代 CPU 上，軟體中的 Karatsuba 往往對 ECDSA 等 P-256 無益（ $ n=256 $ , $ w=32 $ 或者 $ w=64 $ )，但可以想像它對於 RSA 中使用的更寬的模數很有用。Karatsuba 乘法可以與蒙哥馬利減法一起使用。這樣做的一個好方法是使用使用 Karatsuba 乘法的大段參數。例如，在整個算法中使用 Montgomery 的實現中可能就是這種情況，使用 Karatsuba 具有寬字和寬乘法器（可能是硬體）。有時 Karatsuba 用於乘法，然後使用 Montgomery 進行單獨的歸約步驟；在這種情況下，Karatsuba 允許的總節省量小於 $ 2 $ , 不管 $ n $ .
我建議Modern Computer Arithmetic了解更多細節；或經典但仍然有用的應用密碼學手冊，尤其是第 14 章。