o(1) 數域篩的時間複雜度
眾所周知，數域篩的時間複雜度可以通過下式計算
$$ \exp\big((C+o(1)) (\log n)^{1/3}(\log \log n)^{2/3}\big) $$ 常數 C 以特殊和通用數域篩變體而聞名。
我的問題是，價值如何 $ o(1) $ 近似為 n 的密碼合理值（例如 $ 2^{1024} \le n \le 2^{4096} $ )?
是否存在已知的上限和下限？
這個問題的原因如下。根據 o(1) 的定義，我們只能得出結論，該值漸近消失。但是對於 n 的任何有界值，該值可以是任何值。因此，在強烈的數學意義上，這個公式對於任何關於實際尺寸分解問題的結論都是無用的。
總結：假設 $ o(1) $ 項為正數，並將其取為零，在該公式隨後用於估計較大值的工作比率的下限的情況下 $ n $ 對於較小的值 $ n $ .
給出的公式，與 $ o(1) $ 術語，給出了NFS的複雜性。如果通過為 $ o(1) $ 項，它產生一個函式 $ n $ 沒有單位，因此不足以計算執行給定算法所需的時間（或努力或成本） $ n $ . 這 $ o(1) $ 術語恰好包含成本的數量級（作為外部指數和正指數的結果） $ \log n $ 學期）。
但是，該公式的一個常見且合法的用途是評估執行 NFS 的工作如何擴展 $ n $ ，通過計算公式給出的不同值的比率 $ n $ （並採用 base-2 日誌以獲取以位為單位的安全變化）。從這個意義上說，問哪個值是有意義的 $ o(1) $ 應該用於給定的 $ n $ .
我不知道，這可能取決於 NFS 的變體（這也對 $ C $ )，以及手頭的硬體。
然而，一種常見的方法是假設這 $ o(1) $ 項為正，外推多大時取為零 $ n $ 需要，因此（如果假設是正確的）從密鑰持有者的角度來看是安全的。
補充評論自我回答：上一段中的實踐範例是 NIST 在FIPS PUB 140-2 實施指南和加密模組驗證程序（2016 年 8 月 1 日更新）中給出的公式，計算正常位力量 $ x $ 的 RSA 公共模數 $ L $ 位為
$$ x;=;{1.923\times\sqrt[3]{L\log(2)}\times\sqrt[3]{(\log(L\log (2)))^2}-4.69\over\log(2)} $$ 這是通過獲得
- 使用 GNFS 複雜度公式的直接轉換 $ C=\sqrt[3]{64\over9} $ 四捨五入到 4 位有效數字；
- 忽略 $ o(1) $ 項，從而獲得 $ x $ 這樣 $ 2^x $ 是對未知單位工作的估計；
- 通過引入加性常數來解決上述問題 $ -4.69 $ （這實際上是一個乘法常數 $ 2^{-4.69/\log(2)} $ 關於所涉及的工作 $ 2^x $ )，確定當 $ L=1024=2^{10} $ ，得到的結果是 $ x=80.000\dots $ ，因為這符合 FIPS 140-2 規範性上下文，並且軼事證據表明，破解常見 80 位對稱加密的成本將小於分解正確生成的 1024 位 RSA 模數的成本。
因此，如果用於估計由 $ L\ge1024 $ 比特從真正的隨機性中正確生成，假設現在大致上實踐的 GNFS 仍然是最好的因式分解算法。