Re: Points on elliptic curves
- From: Jyrki Lahtonen <lahtonen@xxxxxx>
- Date: Mon, 19 Dec 2005 10:15:13 +0200
foaud167 wrote:
Hi I am working with non-supersingular elliptic curves over GF(2^m), with the general form
y^2 + xy = x^3 + a2 * x^2 + a6
My question is how do you solve for y, for a given x (There should be a solution, since every polynomial has a square-root in GF(2^m)) I was thinking along the lines of completing the square, but that didn't work out.
thanx a lot
No, it isn't that simple. The usual formula for solving quadratic equations doesn't apply in characteristic two for the simple reason that you are not allowed to divide by two (because it would amount to dividing by zero, which is a no-no). A crash course follows (for more background see, e.g. Lidl & Niederreiter)
The following construction will take the place of square roots: Let T:GF(2^m)->GF(2) be the trace map, i.e.
T(x)=x+x^2+x^4+...+x^(2^(m-1)).
This is a homomorphism of additive groups, i.e. T(x+y)=T(x)+T(y). As T(x) is a polynomial its kernel cannot have more than 2^(m-1) elements. As T(x) lies in GF(2) for all x in GF(2^m), Im(T) cannot have more than two elements. So it must be that T is onto, and Ker(T) has exactly 2^(m-1) elements. Furthermore we have for all x in GF(2^m) the identity
T(x)=T(x^2). (*)
Consider the mapping S:GF(2^m)->GF(2^m), S(x)=x+x^2. This is also a homomorphism of additive groups. Obviously Ker(S)=GF(2^m), so Im(S) has size 2^(m-1). By equation(*) above
T(S(x))=T(x)+T(x^2)=2T(x)=0
for all x in GF(2^m). Therefore Im(S) is a subset of Ker(T). As the two groups have the same size we must have equality
Ker(T)=Im(S). (**)
What does this have to do with quadratic equations? Identity (**) can be rewritten as: given an element 'a' in GF(2^m) the equation
x^2+x=a (3)
has a solution x in GF(2^m), iff T(a)=0. In fact if x is a solution,
then x+1 is another. We can now say the following about the
general quadratice equation ('a' and 'b' in GF(2^m)):x^2+bx=a. (4)
If b=0 then it has a single solution x in GF(2^m). This is a double root and exists, because all the elements of GF(2^m) have a unique square root. If b is non-zero, then dividing (4) by b^2 gives you the equation
(x/b)^2+(x/b)=a/(b^2),
i.e. an equation of the form (3). So we may conclude that (4) has two roots in GF(2^m), if T(a/b^2)=0, and no roots if T(a/b^2)=1. To summarize: a "trace condition" splits the quadratic equation into two cases more or less equiprobable cases just like the study of the square root of the discriminant does in the case of characteristic not equal to two.
How do you find the solutions? It turns out that there is yet another homomorphism of additive groups L: Ker(T)->GF(2^m) with the property that, if 'a' is in Ker(T), then the solutions of
x^2+x=a
are exactly L(a)=L(a)+1. The above simple substitution then allows you to solve the general quadratic, if you know L. I don't remember the general formula for L without checking out my notes, so I will leave that as an exercise. In the case that m is odd (often true in e.g. crypto applications), the following works
L(x)=x^2+x^8+x^32+...+x^(2^(m-2))
(i.e. a partial sum of T(x), where you only include every other term. For even m it gets messier. The simplest L (AFAIR) looks manageable when m is even, but no divisible by 4, but even that uses an element of GF(4) as a coefficient.
May be the handbook of appliled crypto has something about solving (3). IIRC using a normal basis representation of the elements of GF(2^m) allows for a fast way of explicitly finding the solutions. IIRC that method hides the function L rather nicely :)
Good luck!
Jyrki Lahtonen, Turku, Finland .
- Follow-Ups:
- Re: Points on elliptic curves
- From: foaud167
- Re: Points on elliptic curves
- References:
- Points on elliptic curves
- From: foaud167
- Points on elliptic curves
- Prev by Date: Re: coupled ODE solution (almost)
- Next by Date: Re: help proving that limit of piecewise function DNE
- Previous by thread: Points on elliptic curves
- Next by thread: Re: Points on elliptic curves
- Index(es):
Relevant Pages
|
