What is an elliptic curve? | Not Hacker News!

What is an elliptic curve? | Not Hacker News!

Showing 14 comments

23 days ago

1 reply

Dr Cook has been smashing out some excellent very digestible math content lately.

Edit: Just realised this was posted in 2019.

23 days ago

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.

23 days ago

6 replies

Anyone have a good explanation for why elliptic curves have a 'natural' group law? I've seen the definition of the group law in R before, where you draw a line through two points, find the third point, and mirror-image. I feel like there's something deeper going on though.

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)

aleph_minus_one

23 days ago

1 reply

> 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...

23 days ago

The following is one of my favourite submissions to HN: https://news.ycombinator.com/item?id=44083753

23 days ago

> Are they the _only_ flavour of curve that has a nice geometric group law?

Conic sections have a group law as well, because all non-degenerate conics over the real numbers are isomorphic to a circle with respect to some projective collinearity. This can then be treated as the unit circle inside the complex numbers. They then inherit the corresponding group law.

23 days ago

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). 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 and then the

23 days ago

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.

23 days ago

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.

23 days ago

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.

23 days ago

Nice explanation of elliptic curves especially the emphasis on how the underlying field changes what the curve actually is. The transition from intuitive equations to the formal definition (smooth, projective genus one) is very well done and the Curve1174 example helps clarify why not all elliptic curves look like Weierstrass forms

23 days ago

If folks have ever seen “ed25519” - say when generating an ssh key

https://en.wikipedia.org/wiki/EdDSA

23 days ago

I think a more generic form is:

(y-a)(y-b) = kx(x-c)(x-d)

If you replace kx with ky, k, kx^2, ky^2, you get generalizations for conics or asymptotes etc.

23 days ago

Ola