計算複雜性——真正的指數時間是什麼時候？
我目前正在研究離散對數問題和相關攻擊。我在數學方面很好，但是在估計執行時間時我遇到了問題。更具體地說：如果我們採用像 Baby Step Giant Step 這樣的通用平方算法來處理大小的循環組 $ n $ ，我們通常會到達 $ O(\sqrt{n}) $ 求離散對數的必要操作。由於算法的輸入是以比特為單位測量的，我們得出了一個執行時間 $ O(2^{b/2}) $ 在哪裡 $ b $ 是位長 $ n $ . 到現在為止還挺好。
但是這個論點不適用於矩陣乘法。讓我們來 $ A,B \in Mat(n \times n, \mathbb{Z}) $ , 所以計算 $ A \cdot B $ 顯然需要 $ n^2 $ 中的操作 $ \mathbb{Z} $ . 與上述相反，這被認為是有效的。那麼為什麼我不能像上面那樣爭論並說矩陣乘法也需要指數時間呢？
在更一般的層面上，我經常遇到一些算法需要的論點 $ O(p(n) $ （p(n) 是一些多項式）操作本身可以被有效地計算，因此整個算法被認為是有效的。這與我通過查看 Pollard 的 Rho 等獲得的直覺背道而馳。
我知道我可能在某個地方犯了一個愚蠢的錯誤，但我現在沒有看到它。
謝謝你的幫助！
要確定算法的複雜度等級，您必須確定可以在單位時間內完成哪些操作。例如，典型的 PC 會調整字大小， $ w $ 位（32 位或 64 位）加法和乘法在恆定時間內。
由此，您可以計算出算法需要多少這些原始操作。將兩個相乘 $ 2w $ - 使用教科書乘法的位數，您使用 4 $ w $ -bit 乘以 3 $ w $ -位添加 - 這是 $ O(b^2) $ 一般來說，在哪裡 $ b $ 是位長（ $ w $ 只影響常數）。對於其他乘法算法，它需要 $ O(b^j) $ 對於一些略低的指數。
那麼，方陣乘法呢？
如果矩陣元素是 $ w $ -bit，你可以對元素進行模乘 $ O(1) $ 因此整個矩陣乘以 $ O(n^k) $ ， 在哪裡 $ n $ 是矩陣的寬度和 $ k $ 取決於您使用的乘法算法（ $ k=3 $ 用於教科書矩陣乘法）。
如果您的矩陣元素是 $ b $ -bit，然而，這些中的每一個 $ O(n^k) $ 倍增 $ O(b^j) $ ， 為了 $ O(b^jn^k) $ 總計 - 仍然是多項式。
嬰兒步巨步？
該算法需要 $ O(n^{1/2}) $ 求冪，其中 $ n $ 是順序，所以 $ O(2^{b/2}) $ 為了 $ b $ 位組。這些指數中的每一個也需要時間，這也取決於 $ b $ ：例如，通過平方取冪 $ O(b) $ $ b $ 位相乘。總成本為 $ O(b^c2^{b/2}) $ 對於一些常數 $ c $ .
然而：
- 這只是一個多項式，與指數的數量相比很小。
- 在分析密碼算法時，攻擊的成本通常以使用使用者也需要執行的原語的正常操作的形式給出。