擴展有限域 p^2 中的計算

我想從一個點建構一個失真圖 $ \in \mathbb{F}p $ 至 $ \mathbb{F}{p^2} $ . 如果我有一條橢圓曲線 $ Y^2 = X^3 + 1 $ 超過 $ \mathbb{F}p $ 和一張畸變圖 $ \phi(x,y) \rightarrow (\beta x,y) $ 這給出了形式的一個要點 $ {a+bi : a,b \in \mathbb{F_p}} $ 在 $ \mathbb{F}{p^2} $ . 我的計算是否正確？

這是 pari/gp 的結果：

? p = 821
? q = (p+1)/6
? E = ellinit([0,1]*Mod(1,p));
? until(ellorder(E,P) == q, P = random(E));
? P
%5 = [Mod(277, 821), Mod(137, 821)]

? u = ffgen(p^2, u);
? until(z != 1, z = random(u)^((p^2-1)/3));
? E2 = ellinit([0,1],u);
? elladd(E,P,P)
%9 = [Mod(415, 821), Mod(20, 821)]

elladd(E2,P,P)
%10 = [415, 20]

elladd(E2,P,[z*P[1],P[2]])
%11 = [544*u + 544, 684]

[z*P[1],P[2]]
%12 = [277*u, Mod(137, 821)]

是個 $ u $ 在 pari/gp 中 $ i $ 在 $ a+bi $ ? 在我的計算中，我認為它是這樣的。這是我使用橢圓曲線加法算法所做的：

對於簡單的加法 P+P over $ \mathbb{F}_{821} $ ，我有同樣的答案：

$ \lambda = \frac{3.277^2}{2.137} = \frac{307}{274} = 307.3 \pmod{821} = 100 $

$ x_3 = 100^2 - 277 - 277 = 415 $

$ y_3 = 100.(277-415)-137 = 20 $

所以我得到了相同的點（415,20） $ \mathbb{F}_{821} $

然後之後，與 $ z = i $ ， 我拿 $ \phi(P) = (277i, 137) $ :

$ \lambda = \frac{137 - 137}{277i - 277} = 0 $

$ x_3 = 0 - 277i - 277 = 544 + 544i $

$ y_3 = 0.(277 - ((544 + 544i))-137 = 684 $

我明白了 $ (544 + 544i, 684) \in \mathbb{F}_{821^2} $ 這是pari / gp結果之後的正確答案。

我的計算是否有任何錯誤？

一般來說，一個元素 $ \mathbf F_{p^2} $ 可以表示為 $ a+bu $ 和 $ a,b \in \mathbf F_p $ 和 $ u $ 不可約多項式的根 $ 2 $ 超過 $ \mathbf F_p $ . 如果這個多項式是 $ X^2+1 $ ，那麼我們有 $ u^2 = -1 $ ，在這種情況下，習慣上將其表示為 $ i $ （與復數類比）。沒有什麼要求使用多項式 $ X^2+1 $ ， 然而。在您的情況下，PARI/GP 使用返回的多項式ffinit(821^2)，即多項式 $ X^2+X+1 $ . 因此，在您的計算中使用的關係是 $ u^2 = -(u+1) $ ， 並不是 $ u^2 = -1 $ .

現在，你能強制 PARI/GP 使用多項式嗎？ $ X^2+1 $ ? 是的，但請記住多項式必須是不可約的，並且 $ X^2+1 $ 是不可約的 $ \mathbf F_p $ 當且僅當 $ p \equiv 3 \pmod 4 $ （證明這一點！）。所以它不會以模數工作 $ 821 $ , 但可以工作例如模 $ 823 $ . 您可以通過向 : 提供多項式，而不僅僅是順序來做到這ffgen一點u = ffgen(Mod(1,823)*u^2 + Mod(1,823), 'u)。

此外，雖然在這種情況下，原語 $ 3 $ rd 統一根 $ z $ 等於 $ u $ ，請注意，一般情況下並非如此。

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