What is an elliptic curve? (2019)(johndcook.com)
johndcook.com
What is an elliptic curve? (2019)
https://www.johndcook.com/blog/2019/02/21/what-is-an-elliptic-curve/
14 comments
I find a lot of motivation from topology. If you plot a smooth degree d curve over the complex numbers, it forms a surface of degree g=(d-1)(d-2)/2. In the case of a cubic, we get genus 1, i.e. a torus. Now tori admit a very natural group action, namely addition in (R/Z)^2. And sure enough, if you pick the right homeomorphism, this corresponds to the group action given by the elliptical curve.
Of course, the homeomorphism to (R/Z)^2 does not respect the geometry (it is not conformal). If we want the map to preserve angles, we need our fundamental domain to be a parallelogram instead of a rigid square. The shape of the parallelogram depends on the coefficients of the cubic, and the isomorphism is uniquely defined up to choice of a base point O (mapping to the identity element; for elliptic curves, this is normally taken to be the point at infinity). You still get a group law on the parallelogram from vector addition in the same way, and this pulls back to the precise group action on the elliptic curve.
The real magic is that the resulting group law is algebraic, meaning that a*b can be written as an algebraic function of a and b. This means you can do the same arithmetic over any field, not just the complex numbers, and still get a group action.
Of course, the homeomorphism to (R/Z)^2 does not respect the geometry (it is not conformal). If we want the map to preserve angles, we need our fundamental domain to be a parallelogram instead of a rigid square. The shape of the parallelogram depends on the coefficients of the cubic, and the isomorphism is uniquely defined up to choice of a base point O (mapping to the identity element; for elliptic curves, this is normally taken to be the point at infinity). You still get a group law on the parallelogram from vector addition in the same way, and this pulls back to the precise group action on the elliptic curve.
The real magic is that the resulting group law is algebraic, meaning that a*b can be written as an algebraic function of a and b. This means you can do the same arithmetic over any field, not just the complex numbers, and still get a group action.
>
Anyone have a good explanation for why elliptic curves have a 'natural' group law? [...]
As far as I've seen, the group law is what makes elliptic curves special. Are they the _only_ flavour of curve that has a nice geometric group law?
I asked the same question to a professor who works in topics related to algebraic geometry. His answer was very simple: it's because elliptic curves form Abelian varieties
> https://en.wikipedia.org/wiki/Abelian_variety
i.e. a projective variety that is also an algebraic group
> https://en.wikipedia.org/wiki/Algebraic_group
Being an algebraic group means that the group law on the variety can be defined by regular functions.
Basically, he told to read good textbooks about abelian varieties if one is interested in this topic.
> Are they the _only_ flavour of curve that has a nice geometric group law?
The Jacobian of a hyperelliptic curve (which generalize elliptic curves) also forms an abelian variety. Its use in cryptography is named "hyperelliptic curve cryptography":
> https://en.wikipedia.org/wiki/Hyperelliptic_curve_cryptograp...
I asked the same question to a professor who works in topics related to algebraic geometry. His answer was very simple: it's because elliptic curves form Abelian varieties
> https://en.wikipedia.org/wiki/Abelian_variety
i.e. a projective variety that is also an algebraic group
> https://en.wikipedia.org/wiki/Algebraic_group
Being an algebraic group means that the group law on the variety can be defined by regular functions.
Basically, he told to read good textbooks about abelian varieties if one is interested in this topic.
> Are they the _only_ flavour of curve that has a nice geometric group law?
The Jacobian of a hyperelliptic curve (which generalize elliptic curves) also forms an abelian variety. Its use in cryptography is named "hyperelliptic curve cryptography":
> https://en.wikipedia.org/wiki/Hyperelliptic_curve_cryptograp...
The following is one of my favourite submissions to HN: https://news.ycombinator.com/item?id=44083753
If X is a smooth projective curve over an algebraically closed field k, then we can make a (huge, useless) abelian group Div(X) which is the set of formal sums of points on X. (The "free abelian group" on X).
It would be flippant to say Div(X) is an answer to your question, since it has nothing to do with geometry at all (we can form the free abelian group on any set). An element of Div(X) looks like \sum n_i P_i where n_i are integers and P_i are points on X, and they "add" in the obvious way. The sum doesn't "mean" anything. But we can get to geometry from it.
Inside Div(X) there is a subgroup, Div^0(X), of formal sums of points such that the set of coefficients is zero. Still nothing to do with geometry.
Inside Div^0(X), there is a very interesting subgroup, which is the set of "divisors of functions." Namely, if f is a rational function on X (meaning it's locally a quotient of polynomials), we get an element of Div^0(X) by taking \sum P_i - \sum Q_i where P_i are the zeroes of f and Q_i are the poles (caveat - you have to count them with multiplicity). This is an element of Div(X) but is not obviously an element of Div^0(X) -- this uses the fact that X is projective. Let's call the subgroup that comes this way Princ(X) (for "principal" divisors).
Now we get an interesting group that does have something to do with geometry, which is called Pic^0(X), by taking the quotient Div^0(X)/Princ(X).
Amazing theorem: there is a natural isomorphism from X to Pic^0(X) if and only if X is of genus one, i.e. an elliptic curve. (In general, Pic^0(X) is an abelian variety whose dimension is the genus of the corresponding curve.) This is why only elliptic curves (among the projective ones) are "naturally" groups. The relationship with the usual picture with the lines is that the intersection locus of the lines is the principal divisor associated with a functional that vanishes along the line.
It would be flippant to say Div(X) is an answer to your question, since it has nothing to do with geometry at all (we can form the free abelian group on any set). An element of Div(X) looks like \sum n_i P_i where n_i are integers and P_i are points on X, and they "add" in the obvious way. The sum doesn't "mean" anything. But we can get to geometry from it.
Inside Div(X) there is a subgroup, Div^0(X), of formal sums of points such that the set of coefficients is zero. Still nothing to do with geometry.
Inside Div^0(X), there is a very interesting subgroup, which is the set of "divisors of functions." Namely, if f is a rational function on X (meaning it's locally a quotient of polynomials), we get an element of Div^0(X) by taking \sum P_i - \sum Q_i where P_i are the zeroes of f and Q_i are the poles (caveat - you have to count them with multiplicity). This is an element of Div(X) but is not obviously an element of Div^0(X) -- this uses the fact that X is projective. Let's call the subgroup that comes this way Princ(X) (for "principal" divisors).
Now we get an interesting group that does have something to do with geometry, which is called Pic^0(X), by taking the quotient Div^0(X)/Princ(X).
Amazing theorem: there is a natural isomorphism from X to Pic^0(X) if and only if X is of genus one, i.e. an elliptic curve. (In general, Pic^0(X) is an abelian variety whose dimension is the genus of the corresponding curve.) This is why only elliptic curves (among the projective ones) are "naturally" groups. The relationship with the usual picture with the lines is that the intersection locus of the lines is the principal divisor associated with a functional that vanishes along the line.
There is a purely geometric reason for why elliptic curves have group structure. A geometric shape which is also a group, such that the group operations are smooth maps, has to be homogeneous - it has to look the same from every point[1]. Not just that, if you have a vector at some point, there is a natural way to transport it to every other point on the shape. The only surface (curves over complex numbers are really 2d surfaces) which obeys this property is the torus[2].
[1] Why should the homogeneous property be true? Because in a group, multiplication by g, pushes the identity e to g. M_g(e)=g where. This is a continuous isomorphism of the shape. So the shape looks the same at g as it looks at a (a neigbhourhood of g looks the same as neighbourhood of e). So an 'X' or 'Y' shapes cant be groups, as there are points which are locally unique, but 'O' shape can be a group. Moreover, M_g can also push a fixed non-zero vector v at e to a vector v_g at g.
[2] The Euler characteristic of the torus is 0. A non-zero vector field has index 0. https://en.wikipedia.org/wiki/Poincar%C3%A9%E2%80%93Hopf_the... See the special case of the sphere https://en.wikipedia.org/wiki/Hairy_ball_theorem
[1] Why should the homogeneous property be true? Because in a group, multiplication by g, pushes the identity e to g. M_g(e)=g where. This is a continuous isomorphism of the shape. So the shape looks the same at g as it looks at a (a neigbhourhood of g looks the same as neighbourhood of e). So an 'X' or 'Y' shapes cant be groups, as there are points which are locally unique, but 'O' shape can be a group. Moreover, M_g can also push a fixed non-zero vector v at e to a vector v_g at g.
[2] The Euler characteristic of the torus is 0. A non-zero vector field has index 0. https://en.wikipedia.org/wiki/Poincar%C3%A9%E2%80%93Hopf_the... See the special case of the sphere https://en.wikipedia.org/wiki/Hairy_ball_theorem
Another answer to this: https://en.wikipedia.org/wiki/Cayley–Bacharach_theorem
A second special case of this theorem is Pascal's theorem, which says (roughly) that a variant of the elliptic curve group law also works on the union of a conic C and a line L (this union, like an elliptic curve, is cubic), where the group elements are on the conic. One point O on the conic is marked as the identity. To add points A+B, you draw a line AB between them, intersect that with the fixed line L in a point C, draw a second line CO back through the marked identity point, and intersect again with the conic in D:=A+B. This procedure obviously commutes and satisfies the identity law, and according to Pascal's theorem it associates.
Under a projective transformation, if the conic and line don't intersect, you can send the line to infinity and the conic to the units in (IIRC) a quadratic extension of F (e.g. the complex unit circle, if -1 isn't square in F). Since the group structure is defined by intersections of lines and conics, projective transformations don't change it. So the group is isomorphic to the group of units in an extension of F. If they do intersect ... not sure, but I would guess it instead becomes the multiplicative group in F itself.
The multiplicative group of F can be used for cryptography (this is classic Diffie-Hellman), as can the group of units in an extension field (this is LUCDIF, or in the 6th-degree case it's called XTR). These methods are slightly simpler than elliptic curves, but there are subexponential "index calculus" attacks against them, just like the ones against the original Diffie-Hellman. The attack on extension fields got a lot stronger with Joux's 2013 improvements. Since no such attack is known against properly chosen elliptic curves, those are used instead.
A second special case of this theorem is Pascal's theorem, which says (roughly) that a variant of the elliptic curve group law also works on the union of a conic C and a line L (this union, like an elliptic curve, is cubic), where the group elements are on the conic. One point O on the conic is marked as the identity. To add points A+B, you draw a line AB between them, intersect that with the fixed line L in a point C, draw a second line CO back through the marked identity point, and intersect again with the conic in D:=A+B. This procedure obviously commutes and satisfies the identity law, and according to Pascal's theorem it associates.
Under a projective transformation, if the conic and line don't intersect, you can send the line to infinity and the conic to the units in (IIRC) a quadratic extension of F (e.g. the complex unit circle, if -1 isn't square in F). Since the group structure is defined by intersections of lines and conics, projective transformations don't change it. So the group is isomorphic to the group of units in an extension of F. If they do intersect ... not sure, but I would guess it instead becomes the multiplicative group in F itself.
The multiplicative group of F can be used for cryptography (this is classic Diffie-Hellman), as can the group of units in an extension field (this is LUCDIF, or in the 6th-degree case it's called XTR). These methods are slightly simpler than elliptic curves, but there are subexponential "index calculus" attacks against them, just like the ones against the original Diffie-Hellman. The attack on extension fields got a lot stronger with Joux's 2013 improvements. Since no such attack is known against properly chosen elliptic curves, those are used instead.
> Are they the _only_ flavour of curve that has a nice geometric group law?
For affine conics over the real numbers, the non-degenerate ones are ellipses (affine transform to complex unit circle), hyperbolas (affine transform to y=1/x and use the group law (x,y)(x',y')=(xx',yy')) and parabolas (affine transform to y=x^2 and use (x,y)(x',y')=(xx',yy')).
I was thinking about projective conics, but it turns out there are no algebraic group laws on those, because they're always ill-defined over an algebraically-closed field. Moreover, over the reals and other non-algebraically closed fields k, the definition of a "regular map" needs to consider points with coordinates taking values in the algebraic closure of k.
For affine conics over the real numbers, the non-degenerate ones are ellipses (affine transform to complex unit circle), hyperbolas (affine transform to y=1/x and use the group law (x,y)(x',y')=(xx',yy')) and parabolas (affine transform to y=x^2 and use (x,y)(x',y')=(xx',yy')).
I was thinking about projective conics, but it turns out there are no algebraic group laws on those, because they're always ill-defined over an algebraically-closed field. Moreover, over the reals and other non-algebraically closed fields k, the definition of a "regular map" needs to consider points with coordinates taking values in the algebraic closure of k.
I prefer a more generic form:
(y-a)(y-b) = (x-c)(x-d)(x-k)
By varying terms on both sides or making a term as a constant, you get generalizations for conics etc.
(y-a)(y-b) = (x-c)(x-d)(x-k)
By varying terms on both sides or making a term as a constant, you get generalizations for conics etc.
If folks have ever seen “ed25519” - say when generating an ssh key, and wondered what it meant and how that tiny thing could still be secure
https://en.wikipedia.org/wiki/EdDSA
https://en.wikipedia.org/wiki/EdDSA
Dr Cook has been smashing out some excellent very digestible math content lately.
Edit: Just realised this was posted in 2019.
Edit: Just realised this was posted in 2019.
John is not only smart and knowledgeable, but an incredibly great person to know in general. I worked with him on a project briefly back in 2012 and he stood out as a champion for science, coding, and education. His posts clearly reflect him well.
[flagged]
As far as I've seen, the group law is what makes elliptic curves special. Are they the _only_ flavour of curve that has a nice geometric group law? (let's say aside from really simple cases like lines through the origin, where you can just port over the additive group from R)