橢圓曲線密碼學的離散對數問題的難度如何？
根據定義，離散對數問題是解決以下同餘 $ x $ 眾所周知，一般來說，沒有有效的算法。
$$ \begin{align*} b^x\equiv r&\pmod p\quad(1)\end{align*} $$ 就是找 $ x $ （如果存在的話）對於給定的 $ r,b $ 作為小於素數的整數 $ p $ .
到目前為止我是對的嗎？如果我有任何誤解，請糾正我。
在橢圓曲線密碼學中，據說在 $ P=a\times G $ 我們無法計算 $ a $ 通過知道 $ P $ 和 $ G $ 因為離散對數問題很難解決。我不明白這與等式 1 有什麼關係。我的意思是這兩個問題中只有術語相似嗎？
為了澄清我的問題，讓我們想像一下，未來幾代的天才最終可以通過使用時間的平均硬體設置在可行的時間內完成等式 1 的解決方案。他們提出的算法能夠找到 $ x $ （如果存在）對於任何給定的素數 $ p $ 和任何給定的 $ r, b $ . 現在，我想知道這項發明是否對橢圓曲線密碼學的安全性構成威脅？換句話說，這種算法的知識是否有助於檢索 $ a $ 從 $ P $ ?
如果是，請解釋這種關係是如何定義的以及我們可以計算的數學流程是什麼 $ a $ 從 $ P $ ，我猜這必須通過求解類似於等式 1 的同餘。
如果不是，請告訴我橢圓曲線中離散對數問題的難度與等式 1 的難度有什麼不同，以及為什麼在這裡使用這個術語。
可以為任何有限循環群定義離散對數問題，而不僅僅是以素數為模的乘法群。最著名的例子是你描述的問題，但它不是唯一的。
組可以用乘法表示法（如乘法組模 $ p $ )，所以群操作寫成 $ * $ , $ \times $ , $ \cdot $ 或者只是隱含的。在所有這些情況下，我們採用自然符號來重複使用單個元素的組操作，即 $ b^2:=b*b $ 和類似的概括。因此，循環群的一般離散對數問題 $ C $ 寫成乘法符號生成 $ b $ 給出 $ r\in C $ 找一個整數 $ x $ 這樣 $ b^x=r $ .
其他組用加法表示（這通常保留給阿貝爾組，包括橢圓曲線組）。在這種情況下，組操作表示 $ + $ （但不應將其理解為通常意義上的加法），並且再次使用單個元素重複使用組操作的自然符號，即 $ 2G=G+G $ 等等。當以這種方式編寫時，循環群的離散對數問題 $ C $ 由產生 $ G $ 變成：給定 $ P\in C $ 找一個整數 $ x $ 這樣 $ xG=P $ .
人們認為不同組中的離散對數問題之間沒有明確的轉換。有些組的離散對數問題很容易（例如加法組模 $ p $ , 乘法群模 $ 2^n $ 甚至（在準多項式意義上）乘法群 $ GF(2^n) $ ).
對於乘法群模的特殊情況 $ p $ 最著名的（經典）攻擊是數域篩，它在亞指數時間內解決了問題。這種攻擊只能應用於非常罕見的橢圓曲線（MOV 曲線）類別，而最著名的針對橢圓曲線的通用攻擊是適用於所有組的“平方根”攻擊。
請注意，所有離散對數問題都可以通過Shor 算法在（量子）多項式時間內求解。
讓 $ E $ 是在有限域上定義的橢圓曲線 $ \mathbb{F}_p $ :
$$ E : y^2 = x^3 + Ax + B \text{ with } A, B \in \mathbb{F}_p $$
讓 $ P $ 和 $ T $ 點在 $ E(\mathbb{F}_p) $ . 找一個整數 $ a $ 以便
$$ P =aG $$
這是橢圓曲線的問題。問題可以用對數重寫：
$$ a = log_G (P) $$
您可以將其與“標準”離散對數進行比較：
$$ b^x \equiv r \mod p \Rightarrow x = log_b(r) $$
你現在看到相似之處了嗎？
**注意：**你的天才應該有一個有效的方法來打破它，而不是因為他擁有無限的資源。是的，如果你有一種有效的方法來打破離散對數，你可以使用它的變體來打破橢圓曲線。橢圓曲線加密的要點是，計算比“標準”離散對數係統更快（ecc 有很多不同的其他優點）。