使用固定底數和模數加快模冪運算
有人可以解釋一下，如何 $ a^x \mod N $ 可以加速，當 $ a $ 和 $ N $ 是已知常數嗎？收益有多大，需要什麼資源？
https://www.imperialviolet.org/2013/05/10/fastercurve25519.html
順便提一下：它可以加速 SRP 雜湊蠻力，計算為 $ v = g^x \mod N $ 在哪裡 $ x = hash(username, salt, password) $
一種明顯的方法是預先計算值 $ a^{k_1} \bmod N $ , $ a^{k_2} \bmod N $ , …, $ a^{k_i} \bmod N $ , 和 (取決於 $ x $ ) 將適當的元素相乘。
舉個簡單的例子，如果我們預先計算 $ a^1 \bmod N, a^2 \bmod N, a^4 \bmod N, … a^{2^k} \bmod N $ , 和 (基於 $ x $ 在二進制中，將適當的元素相乘）；這給出了一種平均方法 $ 1/2 log_2 N $ 相乘，這比無需任何預計算即可完成的操作有了明顯的改進。
該論文給出了一個稍微激進的例子（處理 $ x $ 作為基數 16 而不是基數 2）。
但是，您可以做得更好：請參閱本文以了解各種可能性。
注意：如果您在橢圓曲線上執行操作（即進行點加法而不是模乘法），那麼計算元素逆的操作很便宜；即使引用的論文沒有涵蓋這種情況，也可以用來進一步減少操作的數量。
簡而言之：如果你知道 $ (a,N) $ , 你可以通過預先計算一些冪來加快計算速度 $ a $ .
讓 $ x=x_n\dots x_1x_0=\sum_{i=0}^n x_i 2^i $ 是的二進制展開 $ x $ ， 然後讓 $ a_j=a^{2^j}\pmod N $ .
很天真：
$$ a^x \pmod N = \overbrace{a*(a*(a*\dots*(a))\dots))}^{\text{x terms}} $$ 這需要 $ \theta(x) $ 乘法。 傳統的平方和乘法：
$$ a^x \pmod N = a^{x_n \dots x_0} = a^{2^n x_n+ \dots+ x_0} =(a^{2^n})^{x_n} (a^{2^{n-1}})^{x_{n-1}} \dots a^{2^0})^{x_n} =\prod_{i=0}^n a_i^{x_i} $$ 因此，為了使用它進行有效乘法，我們保持產品價值 $ y $ , 和指數變數 $ e $ - 初始化為 $ (y,e)=(1,a) $ . 然後，我們簡單地繼續平方 $ e $ , 相乘 $ y $ 經過 $ e $ 每次我們達到某種權力 $ a^{2^j} $ 為此 $ x_j= 1 $ . 這需要多少工作？好吧，我們必須計算 $ n=\log_2(x) $ 乘法計算 $ a_j $ , 然後平均 $ n/2 $ 乘法計算 $ a^x $ （我們假設“平均值”為 $ x $ 設置了一半的位），最多 $ n $ 乘法。全部的？ $ 2n $ 最差的情況， $ \frac{3}{2}n $ 一般。 平方和乘法的預計算優化
計算每個 $ a_j=a^{2^j}\pmod N $ 提前，當我們計算 $ a^x $ 我們只需要（最多）做 $ n $ 乘法。也就是說，我們根本不需要做任何冪運算。然而，如果 $ x $ 可能非常大，這將涉及儲存大量數據，但是通過儲存其中的一些子集 $ j $ 我們可以減少達到剩餘值所需的求冪次數。此外，如果有人願意，這可以儲存諸如 $ b=a_4*a_2 $ ，這將減少線上計算成本 $ a^{1010b} $ 以查找的成本 $ b=a^{1010b} $ .
決定這種權衡的平衡提供了一個有趣的問題，因為在某些時候儲存過多的權力變得不合理。例如，可以預先計算和儲存 $ a^x\pmod N $ 對全部 $ x\in{0,\dots,2^t} $ . 這將減少計算 $ a^x $ 到查找成本，但這樣的表會有大小 $ \theta(2^t) $ ，這很可能是不切實際的大。