5
$\begingroup$

Let $E$ be an elliptic curve over a binary extension field $GF(2^m)$, with constructing polynomial $f(z)$ be an irreducible, primitive polynomial over $GF(2)$, and let $G(x_g,y_g)$ be a generator point on the curve.

Is there any possibility that two (or more) different $f(z)$ can produce exactly the same GAL group for an elliptic curve (same polynomials as elements)? We do not allow adjustments of coefficients in the curve's equation.

For example, for $GF(2^{233})$ is there any case that e.g. the following irreducible constructing polynomials $f_1(z): z^{233} + z^{74} + 1$ and $f_2(z): z^{233}+z^{159}+1$ to produce identical elliptic curve point groups as elements $\in GF(2^{233})$?

My question definitely relates to a group isomorphism, as a function that maps a 1-1 correspondence between the elements of a group under group operations, but I wonder if it can go beyond that. For example, let a group isomorphism between elements of a Group $GF(2^m)$. Can this isomorphism go beyond group operations for any given tuple of elements $x_i$ and $x_j$ and perserve function mappings beyond group operations? For example, for scalar $k$ and the previously defined ECC generator point $G$, Point $P = k∗G$ is a different point for group $GF(2^m)$ if produced under different irreducible constructing polynomials. My question is if a point like this can indeed perserve more mappings/direct correspondences beyond group operations (in this context, both points $P$ will produce the same field trace, or the same Norm, or Half trace results when solving $z^2+z=λ$.

Thank you for your time,

$\endgroup$
7
  • 3
    $\begingroup$ Do coefficients of $E$ change when $f$ changes? What are "identical elliptic curve point groups"? Do you only mean there is some isomorphism between the two groups, or do you additionally require that isomorphic points have the same $x$ and $y$ coordinates? Unless I err, the first follows from isomorphism of various instances of $\operatorname{GF}(2^m)$ for different irreducible $f$, if we allow for adjustment of coefficients of $E$ per the field isomorphism. Independently, is there a reason to specify that $f$ is primitive? $\endgroup$
    – fgrieu
    Apr 29 at 10:15
  • 1
    $\begingroup$ Thanks @fgrieu, useful comment for clarity. Ok so, first of all, no we do not allow for adjustment of coefficients in the curve's equation. I am talking about exactly the same curve. Second, I am talking about having the exact same coordinates operate in the same way. For example, when calculating the trace $Tr(x)$ of a specific coordinate x, which is an element in GF to solve the Equation $x^2 + x = w$ in Binary Fields, then the Trace should always give the same output in both cases, despite using different $f_1$ anf $f_2$s. $\endgroup$ Apr 29 at 14:10
  • $\begingroup$ I am confused by this. At least to me the phrase the same curve is meaningless without specifying a presentation of the field. Using the field automorphism between the fields defined by $f_1$ and $f_2$ respectively must also be applied to the coefficients of the equation of the elliptic curve. Otherwise it is not the same curve in any sensible way. $\endgroup$ Jun 3 at 5:51
  • $\begingroup$ Anyway, when you do it right, applying the isomorphism to the coefficients in the equation of the curvem the resulting groups will be isomorphic also. Is the distinction between identical and isomorphic clear to you? Sorry for asking, a veteran algebra teacher here :-). $\endgroup$ Jun 3 at 5:58
  • $\begingroup$ @JyrkiLahtonen, afaik a group isomorphism is a function that maps a 1-1 correspondence between the elements of a group under group operations. What I am saying is definitely an isomorphism but I think it goes beyond that. For example, let a group isomorphism between elements of a Group $GF(2^m)$. Can this isomorphism go beyond group operations for any given tuple of elements $x_i$ and $x_j$ and perserve function mappings beyond group operations? For example, [continued] $\endgroup$ Jun 4 at 6:43

1 Answer 1

4
$\begingroup$

Trying to paint a coherent picture while hopefully also answering the question.

Here we use two different polynomials in defining the field $GF(2^{233})$, namely $$f_1(z)=z^{233}+z^{74}+1\qquad\text{and}\qquad f_2(z)=z^{233}+z^{159}+1.$$ They are both irreducible. Actually it suffices to verify that one is irreducible, because they are each others reciprocal polynomials. That is, $$ z^{233}f_1(\dfrac1z)=f_2(z).\tag{1} $$ With these two polynomials we can define two variants of $GF(2^{233})$. Namely the fields $$K_1=GF(2)[z]/\langle f_1(z)\rangle\qquad\text{and}\qquad K_2=GF(2)[z]/\langle f_2(z)\rangle.$$ By the fundamental theorem of finite fields we know that they are isomorphic. The isomorphism is by no means unique (there are $233$ different automorphisms to choose from), but one of them stands out because of $(1)$. If we denote the natural generators $\alpha=z+\langle f_1(z)\rangle\in K_1$ and $\beta=z+\langle f_2(x)\rangle\in K_2$, then, all because of $(1)$, we have an isomorphism $\sigma:K_1\to K_2$ uniquely determined by $\sigma(\alpha)=1/\beta$. This is because $(1)$ says that $1/\beta$ is a root of $f_1(z)$ as is $\alpha$, and an isomorphism of fields must observe such polynomial relations.


If we look at an elliptic curve

$$E:y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6,\tag{2}$$ where $a_1,a_2,a_3,a_4,a_5,a_6\in K_1$, then we can think of the "same" curve as being defined over $K_2$, if we apply the isomorphism $\sigma$ everywhere. We end with $$ E':y^2+a_1' xy+a_3' y=x^3+a_2' x^2+a_4' x+a_6',\tag{2'} $$ where $a_i'=\sigma(a_i)\in K_2$ for all indices $i$. In other words, we replace the coefficients $a_i\in K_1$ with their isomorphic images in $K_2$.

As isomorphisms of fields respect the arithmetic operations, it immediately follows that if a point $P=(x,y)\in K_1\times K_1$ lies on the curve $E$, then $P'=(x',y')\in K_2\times K_2, x'=\sigma(x), y'=\sigma(y)$, is a point on the curve $E'$.

Furthermore, field automorphisms also take lines in $K_1\times K_1$ to lines in $K_2\times K_2$, and this implies that the above mapping (still call it $\sigma$) also takes the addition of $E$ to addition of $E'$, so it is automatically also an isomorphism of the underlying groups of the two elliptic curves. So if $k$ is an integer and $Q=k*P=(u,v)\in E$ is an integer multiple of $P$, then $Q'=k*P'=(u',v')$ where $u'=\sigma(u),v'=\sigma(v)$.

An isomorphism between the underlying fields automatically produces an isomorphism of elliptic curves and their group structures provided that you also apply the isomorphism to the coefficients of the defining equation (like the passage from $E$ to $E'$ above).


Recording the following, just in case. Putting on my algebra teacher's hat :-). A mistake often made by people not well versed in the language of quotient rings of polynomial rings is to equate the coset $z+\langle f_1(z)\rangle$ with the polynomial $z$. Thinking that $z$ could be an element of $K_1$. The following confusion then rears its ugly head. This element is totally unrelated to the element $z+\langle f_2(z)\rangle\in K_2$. The reason I denoted them by $\alpha$ and $\beta$ respectively is exactly to avoid this confusion. It is sometimes convenient to denote the coset of $z$ by $z$ as well, but you can only do this if the field description never changes. Compare with modular arithmetic. Modulo $11$ the coset of $2$ (similarly often just denoted $2$) really is $$\overline{2}=\{2,13,24,35,\ldots,-9,-20,-31,\ldots\}$$ but "the same" coset of $2$ modulo $13$ looks like $$\overline{2}=\{2,15,28,41,\ldots,-11,-24,-37,\ldots\},$$ a totally different animal. It's the same thing with cosets of polynomials.

Caveat: More often than not when there are two alternative definitions of a finite field, the relation between the respective zeros of the two polynomials is more complicated. The case of reciprocal polynomials here is very exceptional. I simply could not resist using it.

$\endgroup$
1
  • $\begingroup$ Thank you, I follow. Most of them are clear to me already, although the specific example in (1) is interesting. Can you clarify if it follows that, given the isomorphism $σ$ over generators $a$ and $b$ specifically in cases with two reciprocal polynomials (as defined by you above), then all mappings between $P$ and $P'$ will produce the same Trace and Norm outputs due to the reciprocal nature of $f_1(z)$ and $f_2(z)$? $\endgroup$ Jun 6 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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