解決困難的問題從∗p從p∗mathbb Z_{p}^{*}什麼時候ppmathbb p接近2n2nmathbb 2^{n}
假設，對於一些安全參數 $ n $ 你選擇一個素數 $ p $ 這樣 $ p = 2^n+c $ 對於一些相對較小的 $ |c| < 2^m << 2^n $ . 我見過這樣的素數被稱為偽梅森素數（如果 $ c < 0 $ )、巴雷特素數或克蘭德爾素數。
選擇這樣的特殊素數 $ p $ 作為基於離散對數問題的有限域方案的群模 $ Z_p^{*} $ 以任何方式削弱任何已知的基於離散對數的問題的難度？我已經看到了這個相關問題的答案，這意味著如果 $ |c| $ 足夠小，幅度 $ n $ 必須加倍以抵消特殊數字欄位篩的效率提高，但有多小 $ |c| $ 必須要申請嗎？
例如，假設 $ n = 2048 $ 和 $ m = 512 $ , 和漢明權重 $ c $ 大約是 $ 256 $ . 這是否足以對抗 SNFS，同時仍保留 Barrett Reduction 實施優化的可能性？
數域篩的複雜度可以從多項式係數的期望大小得到 $ f(x) = x^d + c_{d-1} x^{d-1} + \ldots + c_0 $ ： 如果 $ c_i \le N^{\epsilon/d} $ ，那麼預期的執行時間是
$$ \exp\left(\left(\left(\frac{32(1 + \epsilon)}{9}\right)^{1/3} + o(1)\right) (\log N )^{1/3} (\log \log N)^{2/3}\right), $$ 或者乾脆 $ L[1/3, (32(1 + \epsilon)/9)^{1/3}] $ . 什麼時候 $ \epsilon = 1 $ ，我們得到 $ L[1/3, (64/9)^{1/3}] $ 又名 GNFS，以及何時 $ \epsilon = 0 $ （更精確地 $ o(1) $ ) 我們得到了 SNFS。你的例子在哪裡？
這需要分析在篩分階段測試的數字的平滑機率，除其他因素外，這取決於評估多項式的大小。篩分過程測試形式的整數
$$ F(a,b) = (a - bm) b^d f(a/b) = (a - bm)(a^d + a^{d-1}b c_{d-1} + \ldots + b^d c_0). $$ 如果我們綁定 $ a $ 和 $ b $ 到 $ M $ ， 和 $ m, c_i $ 到 $ N^{1/d} $ ， 的大小 $ F(a,b) $ 由 $ 2(d + 1) M^{d+1} N^{2/d} $ . 在 SNFS 中，由於兩者 $ m $ 和 $ c_i $ 是 $ o(1) $ ，界限要小得多，因為它不攜帶 $ N^{1/d} $ 因素了。
在您的情況下，我們的情況好壞參半：多項式的上部係數將非常小或為 0，而下部係數會更大。例如，有學位 $ 8 $ 和基地 $ 2^{256} $ ，您的範例導致多項式
$$ x^8 + c_1 x + c_0. $$ 這個多項式是稀疏的，是的，但它的預期 $ F(a, b) $ 值大小界限與一般情況相差不遠： $ 2h M^{d+1} N^{2/d} $ ， 在哪裡 $ h $ 是多項式中非零係數的數量。這是一個持續的改進，但不會漸近地改變平滑機率。所以我希望你的建議比隨機素數更容易一些，但不是很明顯。
由於找到好的多項式本身似乎是一門藝術，很難說究竟什麼時候 $ c $ 在 $ 2^n + c $ 變得足夠大以阻止 SNFS。一個好的經驗法則可能是確保至少 $ c_0 $ 是 $ N^{1/d} $ ， 通過設置 $ c>2^{n/d} $ . 自從 $ d $ 是上述大小表達式中的指數，它往往會很小：1024 位數字預計有 $ d $ 的 $ 6 $ 或者 $ 7 $ ; 2048 位可能會使用學位 $ 8 $ ; 和最優漸近表達式 $ d $ 是 $ ((3\log N)/(\log \log N))^{1/3} $ ，所以增長非常緩慢。
在相關的說明中，用於低權重素數的Schirokauer方法在這裡不起作用：它限制了 $ c $ 在 $ L[1/3, c] $ 整數（有符號）權重的 NFS 複雜度 $ w $ 作為
$$ (32/9)^{1/3}((\sqrt{2}w - 2\sqrt{2} + 1)/(w - 1))^{2/3} < c < ((32/9)(2w-3)/(w-1))^{1/3}. $$ 更換 $ w $ 和 $ 256 $ 結果在界 $ 1.9215 < c < 1.9217 $ ，幾乎無法與 GNFS 區分開來。