在二進製欄位上實現 ECC
我應該在二進製欄位*（在 C++ 中）*上為以下類型的方程實現 ECC - $ y^2 + xy = x^3 + ax + b $ ，作為我的項目。我希望包括以下功能：
- 使用者將輸入一個質數 $ m $ ，這將作為二進製欄位的順序為 $ 2^m $ .
- 對於給定的 $ m $ ，將生成不可約多項式。
Q1。AFAIK，沒有有效地找到隨機不可約多項式的方法。唯一的方法是選擇一個隨機多項式並檢查它是否不可約。*（多項式只能是五項式，在某些情況下是三項式）*我的想法是否正確？
- 係數 $ a $ 和 $ b $ 會生成。
Q2。我可以使用隨機數生成器*（具有適當的約束）* 來生成 $ a $ 和 $ b $ 而不是從種子中產生它 $ S $ ? 另外，我看過兩個種子 $ S $ 和參數 $ b $ 被提及。寫這兩個東西的目的是什麼 $ S $ 足以產生 $ b $ ?
- 將列出位於曲線上的各個點。
Q3。要生成所有點，請將 $ x=0, 1, 2 …m-1 $ 並解決 $ y $ 對於類型的方程： $ y^2 + ky = l $ . 在這種情況下如何求平方根？有沒有更好的方法來生成所有積分？
- 將展示 Schoof 算法等計算橢圓曲線上的所有點。（雖然所有的點都已經生成了，但是提出一個算法將是一個額外的優勢）
- 合適的基點 $ P $ 將被選擇以使其具有相當低的輔因子。
Q4。要找到這樣一個點，應該找出每個點的順序。我能想到的唯一方法是：選擇一個點 $ Q $ . 尋找 $ 2Q, 3Q $ 直到點開始重複。因此，一個人得到了訂單。對所有點都這樣做，同時保持最大順序。有沒有更好的方法來實現它？
- 最後，將介紹在二進制場上類似於 ECC 的 El-Gamal 和/或 Diffie Hellman。
我想根據上述情況澄清上述問題。到目前為止，我對ECC的了解還不夠，所以很可能我問了一些無意義的問題，對此我感到非常抱歉。請隨時分享您對這些/任何其他功能的想法，以使項目更有價值。
Q1。
這是一個算法來測試有限域上的單變數非常量單項多項式的不可約性 $ \mathbb F_q $ . （我從 von zur Gathen 和 Gerhard 的現代電腦代數中了解到這一點。）
讓 $ q=p^e $ 成為主力。費馬小定理的推廣表明，對於所有 $ d\geq1 $ ,
$$ x^{q^d}-x ;=;\prod {,f\in\mathbb F_q[x]\text{ monic and irreducible with }\deg f\mid d,} \text. $$ 因此，一元多項式 $ f\in\mathbb F_q[x] $ 是不可約的當且僅當 $ \gcd(x^{q^d}-x,f)=1 $ 對所有人 $ d\in{1,\dots,n-1} $ . 這立即產生了一個用於測試不可約性的算法；這個需要 $ \mathcal O(n^3\log(nq)) $ 正確實施時的基本算術運算。
5.如果您對****Schoof 算法 的高級描述感興趣，請查看我的這篇文章。（特別要注意，實施起來並不簡單。）
Q4。
假設你有一個曲線的素數分解 $ E $ 的組順序（可能使用 Schoof 算法和因子算法獲得），例如
$$ n=\lvert E\rvert=\prod_{i=1}^k p_i^{e_i} \text. $$ 請注意，在任何有限群中，元素的階數除以群階數。因此，您可以輕鬆檢查一個點是否 $ P\in E $ 通過計算冪是生成器 $ [n/p_i]P $ : 如果其中之一是身份，那麼 $ P $ 不是生成器（因為它的順序必須是 $ n/p_i<n $ )，否則為。現在可以證明（使用有限阿貝爾群的分類）隨機選擇的群元素是一個至少具有機率的生成器 $$ \prod_{i=1}^k\left(1-\frac1{p_i}\right)^{e_i} \text, $$ 對於實際目的，它應該“足夠大”（當 $ n $ 有幾個小的素因數），因此你可以通過隨機選擇曲線上的點來找到一個生成器，直到你得到一個。