[curves] Climbing the elliptic learning curve (was: Re: Finalizing XEdDSA)

[Ben Smith]

Hi Ron, everyone,

Here's a rather longish explanation that might be helpful (I hope).
It's sort of a geometric complement to Mike's reply on curve shapes.
It should really be a link to a blog post, I suppose---but in the
absence of a blog, I'm posting it here.

What I'm aiming to do here is
* Connect the Edwards equation with a Weierstrass equation (actually a
Montgomery curve);
* Show how the usual magic birational map appears in a more natural way;
* Resolve Ron's apparent degree-3-vs-degree-4 incompatibility; and
* Explain how we can ignore the whole resolution-of-singularities
issue by simply never having singularities in the first place.

(If the geometric language goes over your head, don't worry; there
will be variables and equations the whole time to to show what I mean.
"Fake it til you make it", etc...)

2016-11-03 20:30 GMT+01:00 Ron Garret <ron at flownet.com>:
> I decided it would be a useful exercise for me to undertake to write such a survey (even if I couldn’t actually finish it), and right away I ran into a snag.  I was trying to reconcile all the different forms of elliptic curve formulas commonly found in the literature, and found the following promising-looking lead on mathworld:
>
> http://mathworld.wolfram.com/EllipticCurve.html
>
> Ax^3 + Bx^2y + Cxy^2 + Dy^3 + Ex^2 + Fxy + Gy^2 + hHx + Iy + J = 0
>
> This is consistent (AFAICT) with the definition given in section 4.4.2.a of Cohen and Frey.  But then there are Edwards curves, which have a x^2y^2 term in them.  How do those fit in?
>
> In fact, as I started thinking about this I realized that Edwards curves are really weird because they’re quartic and not cubic (aren’t they?) and all elliptic curves are supposed to be cubic (aren’t they?)  How can a fourth-order polynomial be birationally equivalent to a third-order polynomial?
>
> I tried taking a look at some of the proofs that Edwards curves are birationally equivalent to Montgomery curves but they went way over my head.  Is there a more elementary way of understanding this?

Degree is a surprisingly subtle concept.  The tricky thing is that
degree is not actually well-defined for curves in affine
coordinates---it only makes sense for projective curves [note 0].  So
we have to be careful about saying that x^3 is a degree-3 term and
x^2y^2 is a degree-4 term, because they're affine, and hence their
"degree" isn't well-defined.

Let's look at two elliptic curves defined by affine plane equations.
First, the Montgomery curve
    M: B*y^2 = x*(x^2 + A*x + 1) ,
which fits neatly into your cubic equation definition above; and
second, the twisted Edwards curve
    E: a*u^2 + v^2 = 1 + d*u^2*v^2 ,
which doesn't.  Assuming we didn't make any pathological choices for
the parameters A, B, a, and d, these curves are both nonsingular *in
the affine plane*.  This is as good a place as any to note that these
elliptic curves have some distinguished points:
 * M has its identity point "at infinity" (hence missing here), and a
special 2-torsion point (x,y) = (0,0);
 * E has the identity point O = (0,1), and a special 2-torsion point P = (0,-1).

I want to relate these two curve shapes to each other, while keeping
things as nonsingular (and concrete) as possible.

As you noted, it *appears* that M has degree 3, while E has degree 4.
That's because we've got a habit of implicitly taking the projective
closure in PP^2, by homogenizing with respect to a new variable.  If
we take (X:Y:Z) as coordinates on the projective plane PP^2, then we
can put x = X/Z and y = Y/Z and clear denominators to get the
projective plane model
    M: B*Y^2*Z = X*(X^2 + A*X*Z + Z^2)   [in PP^2]
for M.  This equation is homogeneous of total degree 3 in X,Y,Z, so we
can legitimately say that in this projective form, M has degree 3.

But what happens if we do the same thing for E?  If we put u = X/Z and
v = Y/Z, then we get the projective plane model
    E: a*X^2*Z^2 + Y^2*Z^2 = Z^4 + d*X^2*Y^2   [in PP^2],
which has degree 4.  If you apply the usual genus formula (genus =
(deg-1)(deg-2)/2), then M has genus 1 (ok), but E seems to have genus
3, which is all wrong [note 1].  That's because this model of E is
singular: there are two singularities, at (X:Y:Z) = (1:0:0) and
(0:1:0).

We're so used to taking projective closures in PP^2 this way that we
tend to call it "the" projective closure, as if it were unique; but
it's not.  And if you start with a smooth affine curve like E,
complete it, and get something singular, then you should immediately
get a feeling that you completed it the wrong way---because you just
tried to squish a projective curve into a space where it wouldn't fit,
and some of its points got mashed together as a result...

...So let's try again.  The natural projective closure for E is *not*
in PP^2, but rather in PP^1 x PP^1, the product of two projective
lines [note 2].  Bear with me for a minute: let (U:S) be coordinates
on one projective line, (V:T) coordinates on another; then
((U:S),(V:T)) is a coordinate system on PP^1xPP^1.  Curves in
PP^1xPP^1 are defined by single equations in U,S,V,T that are
homogeneous with respect to U,S, and simultaneously (but separately)
homogeneous with respect to V,T.  Since the homogeneity for each pair
of coordinates is separate, we have two separate degrees (one with
respect to (U:S), and one with respect to (V:T)), which we package
together as a "bidegree".

Coming back to E, if we put u = U/S, v = V/T, and clear denominators,
then we get a new projective model
    E: a*U^2*T^2 + S^2*V^2 = S^2*T^2 + d*U^2*V^2   [in PP^1xPP^1].
The equation is homogeneous of degree 2 with respect to (U:S), and
homogeneous of degree 2 with respect to (V:T); so E has bidegree
(2,2).  The identity point O = (0,1) on E has product-projective
coordinates ((0:1),(1:1)), and the special 2-torsion point P = (0,-1)
has product-projective coordinates ((0:1),(-1:1)).

What's nice about this version of E is that it's nonsingular, so we
know we're on the right track.  Still, this has come at a cost: we're
now in a funny product projective space, and bidegree (2,2) in
PP^1xPP^1 is no closer to being degree 3 in PP^2...

So our next step is to move from a product projective space into a
"flat" projective space, without squashing anything.  2-dimensional
space didn't work, so let's go to 3-dimensional space: let
(W_0:W_1:W_2:W_3) be coordinates on PP^3.  We can embed PP^1xPP^1 in
PP^3 by mapping ((U:S),(V:T)) to (W_0:W_1:W_2:W_3) =
(U*V:U*T:S*V:S*T).  The result is the quadric surface Q in PP^3
defined by W_0*W_3 = W_1*W_2.  The image of E under this embedding is
the curve in Q defined by
    E: a*W_1^2 + W_2^2 = W_3^2 + d*W_0^2 , W_0*W_3 = W_1*W_2   [in PP^3]
(if you evaluate these two defining equations in (W_0:W_1:W_2:W_3) =
(U*V:U*T:S*V:S*T), then the first will become our product-projective
equation for E, and the second will become 0).  This is only a linear
change of variables away from being in Jacobi intersection form (see
Mike's post). The identity point is now O = (0:0:1:1), while the
special 2-torsion point is now P = (0:0:-1:1).

We've simultaneously done two things here: we've recovered the
classical Jacobi model of an elliptic curve as an intersection of two
quadrics in 3-space, and---probably more interesting to this
list---we've recovered Huseyin Hisil's "extended twisted Edwards
coordinates" (from Hisil-Wong-Carter-Dawson's "twisted Edwards curves
revisited" paper).  Still, while extended coordinates are fast,
they're not the object of this exercise...
Let's continue.  The intersection of two degree-2 surfaces in PP^3 is
a degree-4 space curve, so we've gone from smooth bidegree (2,2) in
PP^1xPP^1 to smooth degree 4 in PP^3.  We want to drop a dimension to
end up in PP^2, and the simplest way to do that is a linear mapping:
that is, a projection away from some point C (the "centre" of the
projection).  Each line through C in PP^3 projects onto a point in
PP^2, and each plane though C projects to a line.  Any plane in PP^3
cuts through our curve in 4 places (degree 4), which means that if we
take C to be any old point of PP^3 then the lines in PP^2 will cut
through the image curve in 4 places: that is, the image curve will
have degree 4 (it will turn out to be a singular quartic: exactly what
we didn't want!).  On the other hand, if we take C to be a point on E,
then any plane through C will intersect the curve in 3 *other* points,
and so any line in PP^2 will intersect the image curve in 3 points:
that is, we'll have a degree-3 image, which is what we want.

So let's project away from the special 2-torsion point P = (0:0:-1:1)
[note 3].  Projecting away from P means writing down a mapping using 3
linear combinations of the 3 polynomials W_0, W_1, and W_2+W_3 (since
these generate the space of linear forms that vanish on P).  If I
start with (W_0:W_1:W_2:W_3) \mapsto (X:Y:Z) = (W_0:W_1:W_2+W_3) then
I get a smooth plane cubic curve, and it's just a matter of eyeballing
the right linear combinations to make sure that the image is the
Montgomery curve (then I use the magic of hindsight to pretend I
wanted those linear combinations all along).

It turns out that if we take (W_0:W_1:W_2:W_3) \mapsto (X:Y:Z) =
(W_0+W_1:W_2-W_3:W_1-W_0), then our E in PP^3 maps down to the
nonsingular projective plane curve
    E: 4/(a-d)*Y^2*Z = X*(X^2 + 2*(a+d)/(a-d)*X*Z + Z^2)   [in PP^2]
---which, if we set B = 4/(a-d) and A = 2*(a+d)/(a-d), is just the
Montgomery curve M!  Not only that,
 * the image of the identity point O is (0:1:0), and
 * the special 2-torsion point P turns out to map to (0:0:1), the
distinguished 2-torsion point on M.

Everything in its right place.

So we've finally arrived: composing all these isomorphisms, we see
that to get from
    E: a*u^2 + v^2 = a + d*u^2*v^2
to
    M: B*Y^2*Z = X*(X^2 + A*X*Z + Z^2)  [in PP^2],
the thing to do is
 (1) take the projective closure of E in PP^1xPP^1 with
        (u,v) \mapsto ((U:S),(V:T)) = ((u:1),(v:1)) ;
 (2) visualise E \subset PP^1xPP^1 in the more-familiar 3-dimensional
space using the Segre embedding
        ((U:S),(V:T)) \mapsto (W_0:W_1:W_2:W_3) = (U*V:U*T:S*V:S*T) ;
 (3) project smoothly back down to the projective plane PP^2, via
        (W_0:W_1:W_2:W_3) \mapsto (X:Y:Z) = (W_0+W_1:W_2+W_3:W_1-W_0) .

Composing the projective maps, we get an isomorphism E \to M defined by
    ((U:S),(V:T)) \mapsto (X:Y:Z) = (U*(V + T):S*(V + T):U*(T - V)) .

If we put everything in the original affine coordinates, with u = U/S,
v = V/T, x = X/Z, and y = Y/Z again, then the isomorphism above
becomes the birational map
    (u,v) \mapsto (x,y) = ( (v+1)/(1-v), (v+1)/(1-v)*1/u )
---which is, reassuringly enough, the one that Bernstein, Birker,
Joye, Lange, and Peters used to connect twisted Edwards curves with
Montgomery curves (in "Twisted Edwards curves").

But now you can see how the birational map appears: first you complete
the affine Edwards curve in the most natural way to get a nonsingular
projective curve, albeit living in a sort of funky product project
space; then you "visualize" the product projective space by embedding
it in the flatter, more familiar PP^3; then you fix your projective
eye at the 2-torsion point image, and looking around you (via the
projection from that point) you see a Montgomery curve.  At the same
time, you've resolved the cognitive dissonance with the apparently
degree-4 Edwards equation: it was never degree 4, it was bidegree
(2,2).  (And we never had to bother with the whole "resolution of
singularities" thing, either!)

[note 0] I would try to explain this properly, but that would require
a whole other (completely OT) post---and this one is far too long and
boring already...  Sorry.

[note 1] What's happening here is that there are two notions of genus:
the arithmetic genus, which is connected to the degree/multidegree of
a particular curve in a given projective space, and the geometric
genus, which is intrinsic to the curve itself.  If you like, the
arithmetic genus measures the equational complexity of a given
presentation of a curve, while the geometric genus measures the true
complexity of the curve itself, independent of its presentation.  The
arithmetic genus can be greater than the geometric genus, but never
less.  The difference between the two is accounted for by the
singularities that we see in a given presentation.  In this case,
we've got arithmetic genus (4-1)(4-2)/2 = 3, then we subtract 2 for
the two plain old nodal singularities that appear at infininty, and
we're left with geometric genus 1, which is what we wanted.

[note 2] This "natural" thing can be made rigorous: PP^1 x PP^1 is the
toric variety connected to the Newton polygon of the affine equation
of E (TMI, I know...)  Something that's interesting about PP^1xPP^1 is
that it completes the affine plane with not one, but *two* "lines at
infinity": a "vertical" one and a "horizontal" one.  That's kind of
appropriate in the Edwards setting, because on some level it reflects
the natural symmetries we have around the x- and y-axes (vertical and
horizontal reflections, corresponding to negation and translation by
the special 2-torsion point); and by the same token it's inappropriate
in the Weierstrass/Montgomery setting, because you don't have that
horizontal symmetry there.

[note 3] This is the one bit where we apply a bit of sleight of hand.
Why did I use the point P as the centre C of the projection?  Well, we
need a point on E, and we only have two obvious choices of points
guaranteed to be on E: the identity point O = (0:0:1:1), and the
2-torsion point P = (0:0:-1:1).  The 2-torsion point P is a bit more
special for E, so I went with that---but if you go with O instead,
then you'll end up with the same mappings, and ultimately the same
isomorphism, composed with translation-by-P (which isn't the end of
the world).



Right, that's enough already!  Enjoy your Mondays,

ben

-- 
You know we all became mathematicians for the same reason: we were lazy.
  --Max Rosenlicht