通用數域篩計算複雜度之間的差異

有人告訴我，通用數域篩適用於計算複雜性 $ e^{\sqrt[3]{\frac{64}{9}+o(1)};(\ln n)^{\frac{1}{3}};(\ln\ln n)^{\frac{2}{3}}} $ . 但是，如果沒有一些計算工作，它應該以計算複雜度執行 $ e^{\sqrt[3]{3+o(1)};(\ln n)^{\frac{1}{3}};(\ln\ln n)^{\frac{2}{3}}} $ .

這似乎沒有太大區別，但根據下表，它是：

如果只是不斷變化，差異怎麼會如此巨大？

通過移動 $ o(1) $ 並且使用初等代數，給出的公式可以用一位數的差異重寫，如

$$ \left(e^{(3^{-2/3});(\ln n)^{\frac{1}{3}};(\ln\ln n)^{\frac{2}{3}}}\right)^{4+o(1)};\text{ and };\left(e^{(3^{-2/3});(\ln n)^{\frac{1}{3}};(\ln\ln n)^{\frac{2}{3}}}\right)^{3+o(1)} $$ 現在有兩點很明顯：

1. 指數從大約 4 變為大約 3；這定性地解釋了為什麼存在如此巨大的差距。
2. 這 $ o(1) $ 擊敗任何外部乘法因子，因此當我們將公式用於任何特定的 $ n $ . 這就解釋了為什麼我們最多可以使用這些公式來大致預測每次攻擊的執行時間（或兩次執行時間的比率）如何隨 $ n $ （然後，不嚴格）；但不能定量預測某些算法的相對執行時間 $ n $ .

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