1

While trying to understand isogeny-based cryptography I stumbled over a passage in a paper by Galbraith. On p.4 he explains how to calculate the image points of an isogeny $\phi:E\to E^{\prime}$:

What about the other 4 points in $E^{\prime}(\mathbb{F}_7)$, such as (3, 0)? These are the image of points on $E$ over an extension of $\mathbb{F}_7$. Consider the point $Q = (1, \alpha)\in E(\mathbb{F}_{7^2})$ where $\alpha \in \mathbb{F}_{7^2}$ satisfies $\alpha^2 = 3$. One can check that $Q$ has order 4, $[2]Q = (0, 0)$, and $\phi(Q) = (3, 0)$.

I'm not sure what $\mathbb{F}_{7^2}$ looks like. If it is a Galois field over a polynomial, how would you translate the polynomials back into $x,y$ values for a point in $\mathbb{F}_{7}$?

Community
  • 1
jvdh
  • 115

1 Answers1

2

$\mathbb{F}_{7^2}$ is a vector space over $\mathbb{F}_7$ of dimension $2$, so you just need to find a basis.

There are plenty of representations of $\mathbb{F}_7$ (as many as the number of irreducible polynomials of degree $2$ over $\mathbb{F}_7$), but Galbraith uses $\mathbb{F}_{7^2}\simeq\mathbb{F}_7[X]/(X^2-3)$. This isomorphism holds because $X^2-3$ is irreducible over $\mathbb{F}_7$ (it has degree $2$ and $3$ is not a square mod $7$).

Hence, an $\mathbb{F}_7$ basis is given by $1,\alpha$, where $\alpha$ satisfies $\alpha^2=3$ ($\alpha=$ the class of $X$, or if you prefer , any root of $X^2-3$ in a fixed algebraic closure of $\mathbb{F}_7$.)

All in all, any element of $\mathbb{F}_{7^2}$ may be written in a unique way as $a+b\alpha,a,b\in\mathbb{F}_7$.

Addition and multiplication are carried on as you may think.

To be precise: $(a+b\alpha)+(c+d\alpha)=(a+c)+(b+d)\alpha$, and $(a+b\alpha)(c+d\alpha)=ac+bd\alpha^2+bc\alpha+ad\alpha=(ac-3bd)+(ad+bc)\alpha$.

Moreover, an element $a+b\alpha$ of $\mathbb{F}_{7^2}$ will lie in $\mathbb{F}_7$ if and only if $b=0$.

GreginGre
  • 15,028
  • "any root of $X^2-7$". Do you mean $X^2-3$? – jvdh Sep 17 '19 at 10:59
  • and could you elaborate on how Galbraith then finds the $\alpha$? By naively plugging in numbers I don't find any $\alpha$ that satisfies $\alpha^2 = 3$ – jvdh Sep 17 '19 at 11:18
  • 1
    Yes, X^2-3. I've corrected the typo. You cannot "find" the $\alpha"$ because it is a pure abstraction, like the imaginary number $i$. he representation of $\mathbb{F}_7$ by the quotient gives you one though: $\alpha=\bar{X}$. However, it does not matter what $\alpha$ is. What matters are its properties, which are summarized in my answer. You should compare with the case of complex numbers. All in all, $\mathbb{C}$ is just $\mathbb{R}[X]/(X^2+1)$ and $i=\bar{X}$. – GreginGre Sep 17 '19 at 12:25
  • Thanks, this was the information I was looking for. The analogue to $\mathbb{C}$ was very helpful. – jvdh Sep 17 '19 at 13:10