從左到右 k 元取冪的平均乘法次數

在The Handbook of Applied Cryptography的第 14 章的 第 617 頁上，從左到右 k 元取冪的平均乘法次數為 $ l\times (2^k-1)/2^k $ ， 在哪裡 $ l=\lfloor t/k\rfloor $ ，即k個單詞的個數 $ t+1 $ 排除前導 1 後的位指數。我的問題是，做殘差 $ t;mod; k $ 位為偶數時需要額外的乘法，因為我們只預先計算奇數 < $ 2^k $ ? 如果這個論點是真的，我應該如何計算正確的平均乘法數？

感謝@galvatron，特別是對於 CPython 的實現。我可以用一個例子來說明我的問題嗎？假設我要計算 $ x^{364086} $ 和 $ k=4 $ . 因為 $ 364086=1011|0001|1100|0110|110_{2} $ , $ t+1=19 $ , $ t=18 $ 和 $ l=\lfloor18/4\rfloor $ =4。我們將預先計算 $ x^3 $ , $ x^5 $ , $ x^7 $ , $ x^9 $ , $ x^{11} $ , $ x^{13} $ , $ x^{15} $ . 然後計算步驟是

1. $ x^{11} $ （來自預計算，沒有乘法）
2. 正方形 $ x^{11} $ 我們有 4 次 $ x^{176} $ . 乘以_ $ x $ ， 我們有 $ x^{177} $
3. 正方形 $ x^{177} $ 2次，我們有 $ x^{708} $ . 乘以_ $ x^3 $ ， 我們有 $ x^{711} $ . 廣場 $ x^{711} $ 2次，我們有 $ x^{2844} $
4. 正方形 $ x^{2844} $ 3次，我們有 $ x^{22752} $ . 乘以_ $ x^3 $ ， 我們有 $ x^{22755} $ . 正方形 $ x^{22627} $ 1次，我們有 $ x^{45510} $
5. 廣場 $ x^{45510} $ 2次，我們有 $ x^{182040} $ . 乘以_ $ x^3 $ ， 我們有 $ x^{182043} $ .平方一次，我們有 $ x^{364086} $ （這是需要一次乘法的殘差位，但這個殘差位需要乘法的機會並不精確 $ (2^{4}-1)/2^{4} $ ，而是 $ (2^{3}-1)/2^{3} $ )

我犯了一個嚴重的錯誤，即第一個 k 位字需要一次乘法，對此我深表歉意。但是我仍然對書中的這個算法有一些疑問。手冊還說，最壞的情況需要 $ l-1 $ 乘法，但在這種情況下，我們必須執行 $ 4>l-1 $ 乘法的次數。

在算法 14.82 中，您將指數分為 $ 2^k $ 視窗。在預計算階段，您將這些“位視窗”編碼為 $ x $ . 所有這些位視窗都將參與乘法運算，除了 $ 000…00_2 $ 視窗，它將被編碼為 1，因此沒有乘法（我假設 $ x\cdot 1 $ 是微不足道的）。

訣竅是：平均而言，你同樣有可能使用另一個 $ 2^k - 1 $ 位視窗。另一種說法是你有一個機率 $ \frac{2^k-1}{2^k} $ 選擇一個不是的位視窗 $ 000…000_2 $ . 我們將指數分割成多少個位視窗？恰恰 $ \lfloor{t/k}\rfloor $ ， 或者 $ l $ .

所以乘法的平均次數（不是預先計算或平方）是 $ l\cdot \frac{2^k-1}{2^k} $ . 您根本不必擔心剩餘位的均勻性。

建議

在實踐中，14.85（滑動視窗方法）在實踐中更有效，即使很難計算它所採取的步驟數（如第 617 頁所述）。如果您正在嘗試實現某些東西，請檢查一下。作為一個真實的例子，CPython 是 Python 的常用 C 實現，使用 14.82 進行大型模冪運算。他們選擇 $ k=5 $ 因為這在實踐中似乎運作良好。

例子

我從這裡複製了一個例子來計算乘法。

查看第 615 頁的算法 14.82，假設我想計算 $ x^{250} $ 然後讓 $ k=2 $ ， 或者 $ b=2^2=4 $ . 寫 $ 250 = (11111010)_2 $ . 有一個視窗 $ 2 $ ， 你有 $ 11|11|10|10 $ .

首先，讓我們製作預計算表：即使我們只需要 $ 11_2 $ 和 $ 10_2 $ ，無論如何，讓我們遵循 14.82：

$ 00_2\rightarrow 1 $

$ 01_2\rightarrow x $

$ 10_2\rightarrow x\cdot x = x^2 $

$ 11_2\rightarrow x^2 \cdot x = x^3 $

我們有四個“位視窗”，只有 $ 3 = 4-1 $ 其中將涉及乘以不是的東西 $ 1 $ .

現在，在算法中，步驟 3.1 是“平方”步驟，除了我們乘以 $ x^{2^2} $ 每一次。在每個“平方”步驟之後，我們都有一個使用上表的乘法步驟。因此，我們一次取兩個位：

$ 11_2: x^3, x^3 $

$ 11_2: (x^3)^4=x^{12}, x^{12}\cdot x^3 = x^{15} $

$ 10_2: (x^{15})^4=x^{60}, x^{60}\cdot x^2 = x^{62} $

$ 10_2: (x^{62})^4=x^{248}, x^{248}\cdot x^2 = x^{250} $

中間一列是平方步驟（3.1），右一列是乘法步驟（3.2）。

所以這給了我們 $ 2 $ 預計算階段的乘法， $ 6 $ 平方（或 $ 3 $ “提高到四分之二”），以及 $ 3 $ 乘法。

在這個例子中， $ t=8 $ ， 所以 $ l = 4, 2^k = 4 $ ，所以公式給出 $ 4 \cdot 3/4 = 3 $ .

如果你做同樣的事情 $ k=3, b = 8 $ ， 你得到 $ 6 $ 預計算乘法， $ 6 $ 平方和 $ 2 $ 乘法。在這種情況下，我們的公式給出 $ l = \lfloor{8/3}\rfloor = 2 $ ， 和 $ 2^k = 8 $ ，所以我們計算 $ 14/8 \approx 2 $ 乘法。足夠接近？

引用自：https://crypto.stackexchange.com/questions/47659