了解 Baby-Step 巨步算法和離散對數

研究 Baby-Step/Giant-Step 算法，我有幾個問題：

1. 在算法中， $ p $ 是組的順序， $ x $ 是解決方案。我們重寫 $ x = i * m + k $ ，但我們為什麼要 $ m =\lfloor\sqrt{p}\rfloor $ ，而不是其他類似的東西 $ \lfloor {p/2}\rfloor $ ?
2. (a) 時間複雜度為 $ O(\sqrt{p}) $ . 如果我們足夠大 $ p $ ，那為什麼群內的離散對數計算難計算 $ G $ 這樣的順序 $ p $ ?

(b) 據說離散對數計算在素數階群中是困難的，特別是在子群（階 $ q $ ) 的強素數組 (like order $ p = 2*q + 1 $ , $ q $ 和 $ p $ 是素數）；這是為什麼？

1. 在算法中， $ p $ 是組的順序， $ x $ 是解決方案。我們重寫 $ x = i * m + k $ ，但我們為什麼要 $ m =\lfloor\sqrt{p}\rfloor $ ，而不是其他類似的東西 $ \lfloor {p/2}\rfloor $ ?

Big Step-Little Step 所用時間為 $ O( m + p/m ) $ （這 $ O(m) $ 術語來自迭代各種 $ k $ 價值觀 $ O(p/m) $ 術語來自迭代各種 $ i $ 價值觀。

應該很容易看出，如果 $ m \approx \sqrt{p} $

2. (a) 時間複雜度為 $ O(\sqrt{p}) $ . 如果我們足夠大 $ p $ ，那為什麼群內的離散對數計算難計算 $ G $ 這樣的順序 $ p $ ?

如果 $ p $ 相當大，那麼 $ \sqrt{p} $ 也很大（即使它沒有那麼大 $ p $ ); 例如，如果我們想要 $ \sqrt{p} \ge 2^{128} $ 所以 Big Step-Little Step 所走的步數大得不可行，我們只取 $ p \ge 2^{256} $ .

請注意：如果我們在小組中工作 $ \mathbb{Z}^*_p $ ，那麼除了通用的 Big Step-Little Step（和 Rho）算法之外，還有其他針對 Discrete Log 問題的攻擊；因此我們通常需要一個更大的 $ p $

2. (b) 據說離散對數計算在素數階群中是困難的，特別是在子群（階 $ q $ ) 的強素數組 (like order $ p = 2*q + 1 $ , $ q $ 和 $ p $ 是素數）；這是為什麼？

如果我們在小組中工作 $ \mathbb{Z}^*_p $ （即乘法群模 $ p $ )，好吧，那個組有一個大小 $ p-1 $ ; 任何素數子群都有一個大小 $ q $ 這是一個除數 $ p-1 $ . 一種方法（但不是唯一的方法）來確保有一個好的 $ q $ 是做 $ p $ “安全素數”，即這樣的素數 $ q = (p-1)/2 $ 也是素數。

另一方面，這僅適用於組 $ \mathbb{Z}^*_p $ ; 如果你去（比如說）橢圓曲線組，沒有相應的理由更喜歡安全素數（無論是對於特徵還是組大小）。

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