Computations in extended finite field p^2

Question

I would like to construct a distortion map from a point $\in \mathbb{F}_p$ to $\mathbb{F}_{p^2}$. If I have an elliptic curve $Y^2 = X^3 + 1$ over $\mathbb{F}_p$ and a distortion map $\phi(x,y) \rightarrow (\beta x,y)$ that gives a point of the form $\{a+bi : a,b \in \mathbb{F_p}\}$ in $\mathbb{F}_{p^2}$. Do my computations are the right ones ?

Here is the results of 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)]

Is the $u$ in pari/gp the $i$ in $a+bi$ ? I consider it as such in my computations. Here is what I did using the elliptic curve addition algorithm :
For the simple addition P+P over $\mathbb{F}_{821}$, I have the same answer :

$\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$

So I get the same point (415,20) for the case in $\mathbb{F}_{821}$
Then after, with $z = i$, I take $\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$

And I get the point $(544 + 544i, 684) \in \mathbb{F}_{821^2}$ which is the right answer following the result of pari/gp.
Do I have any errors in my computations ?

Answer 1

Generally, an element of $\mathbf F_{p^2}$ can be represented as $a+bu$ with $a,b \in \mathbf F_p$ and $u$ a root of an irreducible polynomial of degree $2$ over $\mathbf F_p$. If this polyomial is $X^2+1$, then we have $u^2 = -1$, and in that case it is customary to denote it by $i$ (in an analogy with complex numbers). There is nothing that mandates the use of the polynomial $X^2+1$, however. In your case, PARI/GP uses the polynomial returned by ffinit(821^2), which is the polynomial $X^2+X+1$. Thus the relation to use in your computations is $u^2 = -(u+1)$, and not $u^2 = -1$.

Now, can you force PARI/GP to use the polynomial $X^2+1$? Yes, but remember that the polynomial must be irreducible, and $X^2+1$ is irreducible over $\mathbf F_p$ if and only if $p \equiv 3 \pmod 4$ (prove this!). So it will not work modulo $821$, but would work for example modulo $823$. You do it by providing the polynomial, instead of just the order, to ffgen: u = ffgen(Mod(1,823)*u^2 + Mod(1,823), 'u).

Also, although in this case the primitive $3$rd root of unity $z$ equals $u$, note that it is not true in general.