1
$\begingroup$

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 ?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I felt like I should add the proof to "prove this". If $p \equiv 3 \pmod 4$, then for any quadratic residue $r \pmod p$, $-r \mod p$ is a nonresidue. $1 \pmod p$ is trivially a residue, so $(-1) \pmod p$ is not. Since the roots don't exist in $\mathbf F_p$, $X^2+1$ is irreducible. For the other way around, if $p \equiv 1 \pmod 4$, the opposite is true with $(-1) \pmod p$ being a residue. Then $X^2+1$ can be factored and is reducible: namely with $p=821$, $X^2+1 = (X-295)(X-526)$. For the remaining case $p=2$, $X^2+1 = {(X+1)}^2$. $\endgroup$
    – Myria
    Jan 12 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.