是安全的素數p=2ķ±sp=2ķ±sp=2^k pm s和sss作為離散對數模數，比其他人更不推薦？
我將安全素數定義為：素數 $ p $ 什麼時候安全 $ (p-1)/2 $ 是素數。
適當大小的安全素數是與離散對數問題相關的密碼系統模數的標準選擇，例如Diffie-Hellman。
模數 $ p=2^k \pm s $ 和 $ s $ 小做冪 $ \bmod p $ 明顯更簡單（經典歐幾里得除法中的商估計問題幾乎消失了，與乘法相比，模約簡的成本可以忽略不計）。這一點，以及使用非任意的、緊湊儲存的模數的願望，使得傾向於選擇這種 $ p $ . 就像“模數應該是最大的 2048 位安全素數，即 $ p=2^{2048}-1942289 $ ”。
是否有任何主要原因不這樣做，例如離散對數問題的更快算法？
簡短的回答：是的。
可以通過多種方式攻擊離散對數：Baby-step Giant-Step (BSGS)、Pollard 的 Rho、Pohlig-Hellman以及Index Calculus的幾種變體，目前最好的是Number Field Sieve。
讓 $ n $ 成為我們領域的生成器的順序 $ \mathbb{F}_p $ ; 它是 $ n = p-1 $ . 我們正在努力尋找 $ x $ 給定 $ a $ 和 $ b=a^x $ 在上述領域。
Pollard 的 Rho 和 BSGS
在 Baby-step 巨步中，我們試圖找到 $ i $ 和 $ j $ 這樣 $ b(a^{-m})^i = a^j $ ， 在哪裡 $ m = \lceil \sqrt{n} \rceil $ . 一旦我們找到這樣的一對，離散對數 $ x = i m + j $ 如下，如 $ b(a^{-m})^i = a^j \Leftrightarrow a^{x - m i} = a^j \Leftrightarrow x \equiv mi + j \pmod{n} $ .
為此，我們首先計算一個表 $ a^j $ 對全部 $ j $ 取決於 $ m-1 $ . 然後我們遍歷所有 $ i $ 取決於 $ m-1 $ , 並比較 $ b(a^{-m})^i $ 和 $ a^j $ . 忽略算術成本，該方法的執行時間最多為 $ 2(m-1) = O(\sqrt{n}) $ （具有相同的空間要求）。
由於空間要求大，實際中很少使用BSGS。相反，我們轉向 Pollard 的 Rho。這種方法的關鍵是找到一個碰撞的非平凡對 $ (i,j) $ 和 $ (k,l) $ 這樣 $ a^ib^j \equiv a^kb^l $ . 它遵循 $ x = \frac{k-i}{l-j} \pmod{n} $ ， 自從 $ a^i a^{xj} = a^k a^{xl} \Leftrightarrow a^{i + xj} = a^{k + xl} \Leftrightarrow i + xj \equiv k + xl \pmod{n} $ .
因此，Rho 歸結為快速發現碰撞。這可以通過各種算法來完成，弗洛伊德是最古老和最著名的。好消息是我們可以嘗試在沒有大桌子的情況下找到碰撞；不太好的消息是該算法是機率性的，儘管生日悖論告訴我們我們應該預計在大約 $ \sqrt{n} $ 腳步。
在任何情況下，這些攻擊對安全素數都沒有好處，其中順序足夠大 $ \sqrt{n} $ 在計算上是不可行的。
波利格-赫爾曼
Pohlig-Hellman 方法依賴於觀察到存在同態 $ \phi $ 從 $ a $ 和 $ b $ 從他們的訂單組 $ n $ , 到階子群 $ p_i^{e_i} $ 劃分 $ n $ . 一般來說，給定 $ n = p_1^{e_1}p_2^{e_2}\ldots p_m^{e_m} $ ,
$$ \phi_{p_i^{e_i}}(a) = a^{n/p_i^{e_i}} $$ 這允許我們計算離散對數 $ \phi_{p_i^{e_i}}(a) $ 和 $ \phi_{p_i^{e_i}}(b) $ ，這實際上是的離散對數 $ a $ 和 $ b $ 模組 $ p_i^{e_i} $ . 從這個觀察來看，這是一個計算對數模所有素除數的問題 $ n $ （使用上一節中的方法）並使用中國剩餘定理將它們組合在一起。
如果 $ n $ 有許多小的素因數，即它是平滑的，這種方法比 Rho 或 BSGS 快得多。然而，在安全的素數情況下，情況並非如此，因為訂單 $ n $ 是產品 $ 2q $ , 對於一個非常大的 $ q $ . Pohlig-Hellman 在這裡沒有多大幫助。
指數演算
指數微積分是計算離散對數模安全素數的最佳算法的基礎。假設我們知道對數 $ 2 $ 和 $ 3 $ ; 找到對數 $ 12 $ 簡單： $ \log_a12 = 2 log_a2 + log_a3 $ ， 自從 $ 12 $ 因素 $ 2^2\times 3 $ .
我們可以將此方法推廣到任意元素。首先定義因子 base，即所有素數到某個界限 $ B $ . 然後，找到因子基數的所有元素的對數（這是棘手的部分）。最後，因素 $ b $ 到因子基數中，只需添加與您找到的因式分解相對應的所有對數。如果 $ b $ 不完全分解因子基數，相乘 $ b $ 通過一些已知的指數 $ a $ 然後再試一次。
求所有素數的對數 $ B $ 需要一些詭計。它有兩個主要步驟：
- 為了 $ k_i \in [1..n] $ , 至少找到（通常通過篩選） $ \pi(B) $ 元素 $ a^k $ 該因子完全進入因子基。儲存兩者 $ a^{k_i} $ 及其完全分解。
- 現在我們有了線性系統（模 $ n $ ): $$ \begin{eqnarray} e_{1,1} \log_a 2 &+& e_{1,2} \log_a 3 &+& \ldots &+& e_{1,{\pi(B)}} &=& {k_1} \ e_{2,1} \log_a 2 &+& e_{2,2} \log_a 3 &+& \ldots &+& e_{2,{\pi(B)}} &=& {k_2} \ &&&&\ldots&&&& \ e_{{\pi(B)},1} \log_a 2 &+& e_{{\pi(B)},2} \log_a 3 &+& \ldots &+& e_{{\pi(B)},{\pi(B)}} &=& {k_{\pi(B)}} \ \end{eqnarray} $$
- 求解上述線性系統為我們提供了因子基所需的對數。
此方法的執行時，用於適當選擇 $ B $ ， 是 $ \exp{((2+o(1)((\log n)^{1/2}(\log \log n)^{1/2}))} $ . 這不是嚴格的多項式，但對以前的方法有很大的改進。
數域篩
數域篩目前是有限域上整數分解和離散對數的最佳算法。對於離散對數，它類似於上面的指數演算，但有一些主要的修改：
- 我們在數字領域工作 $ \mathbb{Q}[\alpha] $ 和 $ \mathbb{Q}[\beta] $ 而不是整數；但是，在某些條件下，存在從這些欄位到整數的映射。數字欄位由多項式定義 $ f_1 $ 和 $ f_2 $ 學位 $ d_1 $ 和 $ d_2 $ ; 必須存在一個整數 $ m $ 這樣 $ f_1(m) = f_2(m) = 0 \pmod{p} $ .
- 因子基由兩者中的素數構成 $ \mathbb{Q}[\alpha] $ 和 $ \mathbb{Q}[\beta] $ , 上限 $ B_1 $ 和 $ B_2 $ .
- 在篩分過程中，我們尋找對 $ (x,y) $ 這樣 $ N_{f_1}(x + \alpha y) $ 和 $ N_{f_2}(x + \beta y) $ 是 $ B_1 $ 和 $ B_2 $ -smooth，分別在哪裡 $ N_{f_i} $ 是（誰）給的 $$ N_{f_i}(x + \alpha y) = y^{d_i} f_i(x/y) $$
數域篩的速度取決於尋找的速度 $ (x,y) $ 有流暢的規範 $ N_{f_i}(x,y) $ . 反過來，機率 $ N_{f_i}(x,y) $ 光滑與它的大小有關：它越小，就越有可能是光滑的。反過來，大小 $ N_{f_i}(x,y) $ 由 $ x $ 和 $ y $ （顯然），但也通過係數 $ f_i $ ！什麼時候 $ f_i $ 具有非常小的係數，數域篩變得漸近更快，從
$$ \exp ( (1.923 + o(1))( (\log n)^{1/3}(\log \log n)^{2/3}) $$ 到
$$ \exp ( (1.526 + o(1))( (\log n)^{1/3}(\log \log n)^{2/3}). $$ 當一個人選擇一個素數時 $ p $ 很接近 $ 2^k $ ，很容易找到具有根模的稀疏多項式 $ p $ . 在你的例子中， $ p = 2^{2048} - 1942289 $ ，我們可以找到度數 $ 8 $ 多項式
$$ x^8 - 1942289, $$ 自從 $ 2^{2048} - 1942289 = (2^{256})^8 - 1942289 $ . 該多項式具有非常小的係數，這使得該欄位中離散對數的數字欄位篩選比隨機 2048 位素數更快。