橢圓曲線的安全性與正常離散對數相比如何？
介紹：
EC 經常與 RSA 進行比較，但更安全的離散對數版本怎麼樣？
所有 3 都可以歸結為問題：
$$ b = g^a \mod{P} $$
在 RSA 中 $ P $ 是兩個素數的乘積。為了解決離散對數“只是”一個因式分解 $ P $ 是必須的。與其他兩種情況不同 $ a,b $ 已知並且 $ g $ 被搜尋。
但如果 $ P $ 是一個素數，問題可能會變得更加困難。它取決於因式分解 $ P-1 $ 因為 $ P-1 $ 也等於不同元素的數量。
據我所知，最好的選擇是“安全的素數” $ P = 2 q +1 $ 和 $ q $ 一個素數。這個離散對數可以解決 $ \mathcal{O}(\sqrt{q}) $ 和 $ q $ 最大的主要因素（使用 Pollard 算法）。
在 EC $ P $ 也是素數，但元素的數量可以不同（但仍然 $ \approx P $ ）。例如，它可以用Schoof 算法來確定。在safecurves.cr.yp.to中可以找到許多安全橢圓曲線。經測試的安全曲線 $ 2^3 \cdot q $ 元素（與 $ q $ 一個大素數）。Afak 解決這些問題也需要 $ \mathcal{O}(\sqrt{q}) $ 時間。
問題：
給定正態數和橢圓曲線的離散對數求解問題（mod a prime $ P_i, P_e $ ）。給定一個有效的生成器 $ g_i, g_e $ 和一個可能的結果 $ b_i, b_e $ .
$$ \text{normal: } b_i = g_i^{a_i} \mod P_i $$ $$ \text{elliptic curve: } b_e = g_e^{a_e} \mod P_e $$
讓橢圓曲線有 $ N_e = 2^3 \cdot q $ 不同的元素與 $ q $ 一個大素數（以這種方式選擇的其他變數）。
讓$$ P_i = 2 \cdot q +1 $$
兩個問題的求解時間是否相同 $ \mathcal{O}(\sqrt{q}) $ ?
（由於乘法時間不同，我們忽略了每一步計算時間的線性因素）
獎勵問題：
還有哪些因素會影響求解速度？
BQ1.) 來自 safecurves.cr.yp.to 的一些曲線的元素數也具有以下屬性： $ N_e -1 = 3 \cdot r $ 和 $ r $ 一個大素數。這有什麼影響嗎？
BQ2.) 有因式分解 $ P_e -1 $ 對安全有影響嗎？
BQ3.) 有因式分解 $ q-1 $ 對安全有影響嗎？（對於正常和 EC）
編輯：更新
- 看起來“數字歸檔篩”可以比 Pollard 的算法做得更好（ $ \mathcal{O}(\sqrt{q}) $ ）。要在 EC 上使用它，嵌入需要很小 -> 選擇一個大的
- 除了安全的黃金地段 $ P_i $ 也應該不接近 $ p^n $ 和 $ p $ 像一個小素數 $ 2,3,.. $
$ \rightarrow $ 假設：所以有區別嗎？
據我所知，最好的選擇是“安全的素數” $ P=2q+1 $ 和 $ q $ 一個素數。
這是給定尺寸的最佳選擇 $ P $ ，但不適用於給定大小 $ q $ . 看到這個。
這個離散對數可以解決 $ \mathcal{O}(\sqrt{q}) $ 其中 q 是最大的素因數（使用 Pollard 的 (Rho) 算法）。
基本上是的（小警告： $ \mathcal{O}(\sqrt{q}) $ 不是努力，而是大小整數的乘法次數 $ P $ ， 和 $ P>q $ ，因此努力至少增長了一個因子 $ \ln P,\ln\ln P $ ）。可以用這種方法和努力解決DLP並不意味著需要這種方法或努力。而如果 $ P $ 是一個安全的素數，有一些方法（包括 Number Field Sieve）需要較少的努力。再次，看到這個。
Do (DLP 在適當的橢圓曲線的一個子組中，一方面， $ \mathbb Z_P^* $ 另一方面）具有相同的求解時間 $ \mathcal{O}(\sqrt{q}) $ （群運算，其中素數 $ q $ 是子群的順序）？
是的，當使用 Pollard 的 Rho 算法時。該算法被認為在橢圓曲線情況下是最優的，並且對於 $ P $ 在足夠大的 $ \mathbb Z_P^* $ 案子。
不，什麼時候 $ P $ 是一個安全的素數（並且大到足以使 DLP 變得不平凡），並且使用數字域篩選器來處理子組中的 DLP $ \mathbb Z_P^* $ .
注意：我不知道數字場篩可以用來在適當的橢圓曲線（子）組中求解DLP；如果它比 Pollard 的 Rho 算法更有效，那將是一個巨大的驚喜。