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 <r...@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 _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves