As I wrote in the comments, I was the record holder, twice, in the 90s:
Fermigier, Stéfane - Un exemple de courbe elliptique définie sur Q de rang ≥19. (French) [An example of an elliptic curve defined over Q with rank ≥19] C. R. Acad. Sci. Paris Sér. I Math. 315 (1992), no. 6, 719–722.
Fermigier, Stéfane - Une courbe elliptique définie sur Q de rang ≥22. (French) [An elliptic curve defined over Q of rank ≥22] Acta Arith. 82 (1997), no. 4, 359–363.
As a professional and expert I would love to hear your thoughts and opinions on the use of elliptic curve crypto with SSH. There was a concern (unsure of the validity) that NSA/NIST had compromised the algorithm used and ECC was unfit for 'secure' communication.
2048bit RSA has been deprecated since that declaration and while 4096bit is still viable, the smaller key-size of ed25519 is appealing.
Ever since the DUAL_EC_DBRG backdoor[1], trust in cryptographic algorithms set by NIST has been reduced.
In the case of ECC curves, the NIST curves rely on a number of highly specific but unexplained constants. More info about the safety and security of curves can be found at https://safecurves.cr.yp.to/
[Not the OP but I think I understand it well enough to take a whack at an ELI5.]
Elliptic curves are a particular kind of cubic equation, exactly like the quadratic equations you studied in junior high algebra, except with one term being raised to the third power instead of just squared (and a few other conditions). It turns out that these equations have vastly more complicated behavior than quadratics and give rise to a whole host of problems that mathematicians are still working to solve. One of the interesting problems arises when you ask: what are the solutions to the equation if we restrict ourselves only to rational numbers? It turns out that rational solutions to elliptic curve equations can be grouped into families of solutions where each member of the family can be derived from other members by linear operations (addition and multiplication by a constant). The number of such families of solutions is called the rank of the equation. (Note: it's actually a little more complicated than that, but that's the gist of it. See [1] if you want the details.)
It is observed empirically (by solving lots of elliptic curve equations) that the rank tends to be small. Indeed, the elliptic curve that made the news did so because it has a rank of 29, the largest rank currently known. But no one knows if this is the biggest possible (almost certainly not) or if there is an upper bound on the possible rank of an elliptic curve. Solving that would win you a Fields medal.
(Note: there are results on the upper bound of the average rank of families of elliptic curves [2] but that is not the same as an absolute upper bound.)
They're curves (one-dimensional), not surfaces. An example of an elliptic curve is y^2 = x^3 + 1. The polynomial P(x,y) = x^3 + 1 - y^2 has degree 3. A surface is a 2 dimensional geometric shape.
Just to be clear, an ellipse is a quadratic curve. Ellipses are not elliptic curves. (They are still curves, though, as long as you restrict to plugging in real numbers, not complex.) The terminology is unfortunate.
- In general, elliptic curves are solutions of P(x, y) = 0 where P is a polynomial of degree 3 in two variables. "Points" on the curve are solutions of this equation.
- If you intersect an elliptic curve with a straight line, you end up with a polynomial in one variable, of degree 3 (in general). Since a polynomial of degree 3 has 3 solutions (in the appropriate context), this means that if you have two points on the curve, and you draw a line through these two points, there is a third aligned with them which belongs to the curve. So we have an operation on the curve, which to every pair of points associates a third point. This can be explicitly calculated.
- It can be proven (again, by explicit calculation) that this operation is associative and commutative, and that there is a "zero" element, i.e. that this operation forms a "group".
Now we want to study these elliptic curves and their associated groups with one additional condition: that the points are rational, i.e. have coordinates that are rational numbers (a/b). For each curve with rational parameters (i.e. the coefficients of the polynomial are rational), we want to study the rational points of this curve.
For some elliptic curves, there is a finite number of points, so the associated group is a finite commutative group.
For other elliptic curves, however, there are infinitely many rational points, and mathematicians have wanted to classify their structure.
A foundational result in number theory known as the Mordell-Weil theorem states that the group of rational points on an elliptic curve over a number field (such as the rationals, ℚ) is finitely generated. In other words, although there may be infinitely many points, they can be expressed as a finite set of points (known as "generators") combined under the group operation. This structure forms what is called a "finitely generated abelian group", which can be decomposed into a direct sum of a finite subgroup (called the "torsion") and a free part of rank r, where r is called the "rank" of the elliptic curve.
This rank "r" essentially measures the "size" of the free part of the group and has deep implications in both theoretical and computational number theory. For example, if r=0, the group is finite, meaning that the set of rational points on the curve is limited to a finite collection. When r>0, there are infinitely many rational points, which can be generated by combining a finite number of points.
So the challenge is to find a curve with a large number of generators. All of these computations (for a given curve at least) are quite explicit, and can be carried out with a bignum library (the numbers tend to get quite large quickly). I used PARI/GP for my thesis.
> - If you intersect an elliptic curve with a straight line, you end up with a polynomial in one variable, of degree 3 (in general). Since a polynomial of degree 3 has 3 solutions (in the appropriate context), this means that if you have two points on the curve, and you draw a line through these two points, there is a third aligned with them which belongs to the curve. So we have an operation on the curve, which to every pair of points associates a third point. This can be explicitly calculated.
> - It can be proven (again, by explicit calculation) that this operation is associative and commutative, and that there is a "zero" element, i.e. that this operation forms a "group".
I feel like it's worth clarifying here that this operation is actually not the group operation, although the group operation is defined in terms of it.
If you going to contradict someone, be specific about it. What is your "the group operation" and how is this not it? A given mathematical object can have more than one group operation defined for it.
Of course for this to make sense you have to have a notion of 0, which is traditionally taken to be the point at infinity (so negation is negating the y-coordinate). It’s been a while since my algebraic geometry classes but IIRC this is just a useful convention.
If like me you're interested in the basics of elliptic curves, point addition, and the abelian groups that result then check the first third of my page at https://curves.xargs.org. It only gets you half way to an understanding of this article but might leave you less mystified.
You can also continue through the rest of that page to see how we use this math in cryptography, such as in key exchange.
That sounds great and I'll try to look. I liked Neal Koblitz's book "A Course in Number Theory and Cryptography" a while back, another resource that might be of interest.
I was going to ask if the math articles from Quanta magazine are a "Matt Levine" situation where only one person can write so well, but I see only six articles by this author there, so maybe it's an editor doing the magic. All I know is this makes math so accessible and that's not easy.
I too love Quanta. It's funded by an extremely wealthy math guy as a public service; they have the luxury of affording excellent journalists who all seem to me to have graduate degrees in the area they cover, but have not lost the power of communication in exchange. Just a very nice gift to the world.
> Simons shunned the limelight and rarely gave interviews, citing Benjamin the Donkey in Animal Farm for explanation: "'God gave me a tail to keep off the flies. But I'd rather have had no tail and no flies.' That's kind of the way I feel about publicity."
I'm glad to read about billionaires with non-poisonous personalities. I'd prefer a world where no individual held such relative power, but next best is a world in which the dreadful oligarchs have foils to balance them out slightly.
I understood a fair bit of it but only because I've been studying elliptic curves for a while - Quanta does a good job of straddling the line between informing and educating, but they usually err on the side of presenting results rather than proving or explaining them.
>...but they usually err on the side of presenting results rather than proving or explaining them
And that's exactly what I like about it. They are a news site, hence they present the news. If the news presenters start to chime in you get what you see at CNN / Fox etc, and that's called propaganda, not news. I want news.
I think part of the reason why 3 is special is because you get a lot of bang for your buck. Order 3 is a low order polynomial that is relatively easy to analyse, but already gives tremendous mathematical properties.
For example, the points of elliptic curves form groups. The operation of combining the points is described in the article (draw a straight line through two points and mirror in x-axis).
That means that all the theorems that are proven for Groups, are also true for elliptic curves.
But I think there are many more exciting properties
Amateur here (just studying abstract algebra for hobby). I’m also very curious for more reasons.
You can get some higher degree examples (y squared = a degree 4 polynomial, for example), but degree 3 is special. An arbitrary polynomial of degree 4 and higher lack a rich structure (as far as we can tell). You can try to get around it by embedding the curve in a higher dimensional object, but it doesn't get you as far. (This is the idea behind hyperelliptic curve cryptography, for example.)
This discovery was already commented a few months ago:
https://news.ycombinator.com/item?id=41475177
As I wrote in the comments, I was the record holder, twice, in the 90s:
Fermigier, Stéfane - Un exemple de courbe elliptique définie sur Q de rang ≥19. (French) [An example of an elliptic curve defined over Q with rank ≥19] C. R. Acad. Sci. Paris Sér. I Math. 315 (1992), no. 6, 719–722.
Fermigier, Stéfane - Une courbe elliptique définie sur Q de rang ≥22. (French) [An elliptic curve defined over Q of rank ≥22] Acta Arith. 82 (1997), no. 4, 359–363.
Ever since the DUAL_EC_DBRG backdoor[1], trust in cryptographic algorithms set by NIST has been reduced.
In the case of ECC curves, the NIST curves rely on a number of highly specific but unexplained constants. More info about the safety and security of curves can be found at https://safecurves.cr.yp.to/
For now, Curve25519 is considered a good bet.
[1] https://en.wikipedia.org/wiki/NIST_SP_800-90A#Backdoor_in_Du...
2048bit RSA is not deprecated...
NIST has deprecated it for government use after 2030, just not today.
well, deprecated does not mean it stops, just that it comes with warnings, so not 2030 either.
It puts it in the same category as triple DES.
Just saw this, congratulations! Would you mind giving an ELI5 explanation for a wider audience?
[Not the OP but I think I understand it well enough to take a whack at an ELI5.]
Elliptic curves are a particular kind of cubic equation, exactly like the quadratic equations you studied in junior high algebra, except with one term being raised to the third power instead of just squared (and a few other conditions). It turns out that these equations have vastly more complicated behavior than quadratics and give rise to a whole host of problems that mathematicians are still working to solve. One of the interesting problems arises when you ask: what are the solutions to the equation if we restrict ourselves only to rational numbers? It turns out that rational solutions to elliptic curve equations can be grouped into families of solutions where each member of the family can be derived from other members by linear operations (addition and multiplication by a constant). The number of such families of solutions is called the rank of the equation. (Note: it's actually a little more complicated than that, but that's the gist of it. See [1] if you want the details.)
It is observed empirically (by solving lots of elliptic curve equations) that the rank tends to be small. Indeed, the elliptic curve that made the news did so because it has a rank of 29, the largest rank currently known. But no one knows if this is the biggest possible (almost certainly not) or if there is an upper bound on the possible rank of an elliptic curve. Solving that would win you a Fields medal.
(Note: there are results on the upper bound of the average rank of families of elliptic curves [2] but that is not the same as an absolute upper bound.)
---
[1]https://en.wikipedia.org/wiki/Rank_of_an_elliptic_curve
[2] https://en.wikipedia.org/wiki/Rank_of_an_elliptic_curve#Uppe...
This is a fantastic ELI5, thank you!
Thanks! I try hard to produce quality technical pedagogy, so you just made my day.
Not exactly the 5 year old level though, "you studied in junior high algebra".
Thank you for sharing, and I'm still looking for ELI5 though, because I don't remember algebra class that well.
>Solving that would win you a Fields medal
it would not win me a Fields medal: ageism, it's only for under 40s.
Youd probably get the Abel prize (which has a significantly larger cash prize)
I strongly doubt that's the primary factor preventing you winning.
For the longest time I thought elliptic curves where quadratic curves.
Wouldn't it had been more accurate to name them elliptic surfaces?
The name derives from the fact that they originally arose in connection with trying to determine the arc length of an ellipse. See:
https://people.math.rochester.edu/faculty/doug/mypapers/wayn...
They're curves (one-dimensional), not surfaces. An example of an elliptic curve is y^2 = x^3 + 1. The polynomial P(x,y) = x^3 + 1 - y^2 has degree 3. A surface is a 2 dimensional geometric shape.
Just to be clear, an ellipse is a quadratic curve. Ellipses are not elliptic curves. (They are still curves, though, as long as you restrict to plugging in real numbers, not complex.) The terminology is unfortunate.
Well, the basics, oversimplified, are this:
- In general, elliptic curves are solutions of P(x, y) = 0 where P is a polynomial of degree 3 in two variables. "Points" on the curve are solutions of this equation.
- If you intersect an elliptic curve with a straight line, you end up with a polynomial in one variable, of degree 3 (in general). Since a polynomial of degree 3 has 3 solutions (in the appropriate context), this means that if you have two points on the curve, and you draw a line through these two points, there is a third aligned with them which belongs to the curve. So we have an operation on the curve, which to every pair of points associates a third point. This can be explicitly calculated.
- It can be proven (again, by explicit calculation) that this operation is associative and commutative, and that there is a "zero" element, i.e. that this operation forms a "group".
Now we want to study these elliptic curves and their associated groups with one additional condition: that the points are rational, i.e. have coordinates that are rational numbers (a/b). For each curve with rational parameters (i.e. the coefficients of the polynomial are rational), we want to study the rational points of this curve.
For some elliptic curves, there is a finite number of points, so the associated group is a finite commutative group.
For other elliptic curves, however, there are infinitely many rational points, and mathematicians have wanted to classify their structure.
A foundational result in number theory known as the Mordell-Weil theorem states that the group of rational points on an elliptic curve over a number field (such as the rationals, ℚ) is finitely generated. In other words, although there may be infinitely many points, they can be expressed as a finite set of points (known as "generators") combined under the group operation. This structure forms what is called a "finitely generated abelian group", which can be decomposed into a direct sum of a finite subgroup (called the "torsion") and a free part of rank r, where r is called the "rank" of the elliptic curve.
This rank "r" essentially measures the "size" of the free part of the group and has deep implications in both theoretical and computational number theory. For example, if r=0, the group is finite, meaning that the set of rational points on the curve is limited to a finite collection. When r>0, there are infinitely many rational points, which can be generated by combining a finite number of points.
So the challenge is to find a curve with a large number of generators. All of these computations (for a given curve at least) are quite explicit, and can be carried out with a bignum library (the numbers tend to get quite large quickly). I used PARI/GP for my thesis.
> - If you intersect an elliptic curve with a straight line, you end up with a polynomial in one variable, of degree 3 (in general). Since a polynomial of degree 3 has 3 solutions (in the appropriate context), this means that if you have two points on the curve, and you draw a line through these two points, there is a third aligned with them which belongs to the curve. So we have an operation on the curve, which to every pair of points associates a third point. This can be explicitly calculated.
> - It can be proven (again, by explicit calculation) that this operation is associative and commutative, and that there is a "zero" element, i.e. that this operation forms a "group".
I feel like it's worth clarifying here that this operation is actually not the group operation, although the group operation is defined in terms of it.
If you going to contradict someone, be specific about it. What is your "the group operation" and how is this not it? A given mathematical object can have more than one group operation defined for it.
In this case there is a negation missing. If a line intersects three points we have A+B+C=0. To get the group law you have to negate a point.
Of course for this to make sense you have to have a notion of 0, which is traditionally taken to be the point at infinity (so negation is negating the y-coordinate). It’s been a while since my algebraic geometry classes but IIRC this is just a useful convention.
This is a fantastic explanation, thank you very much!
If like me you're interested in the basics of elliptic curves, point addition, and the abelian groups that result then check the first third of my page at https://curves.xargs.org. It only gets you half way to an understanding of this article but might leave you less mystified.
You can also continue through the rest of that page to see how we use this math in cryptography, such as in key exchange.
That sounds great and I'll try to look. I liked Neal Koblitz's book "A Course in Number Theory and Cryptography" a while back, another resource that might be of interest.
The animations makes it easier to comprehend indeed. Thanks!
I was going to ask if the math articles from Quanta magazine are a "Matt Levine" situation where only one person can write so well, but I see only six articles by this author there, so maybe it's an editor doing the magic. All I know is this makes math so accessible and that's not easy.
I too love Quanta. It's funded by an extremely wealthy math guy as a public service; they have the luxury of affording excellent journalists who all seem to me to have graduate degrees in the area they cover, but have not lost the power of communication in exchange. Just a very nice gift to the world.
> It's funded
he died in 2024, did he make arrangements to keep funding it or endow it?
I was curious about the rich math guy so I looked it up, leaving this here for the next curious person: https://en.wikipedia.org/wiki/Jim_Simons :)
> Simons shunned the limelight and rarely gave interviews, citing Benjamin the Donkey in Animal Farm for explanation: "'God gave me a tail to keep off the flies. But I'd rather have had no tail and no flies.' That's kind of the way I feel about publicity."
I'm glad to read about billionaires with non-poisonous personalities. I'd prefer a world where no individual held such relative power, but next best is a world in which the dreadful oligarchs have foils to balance them out slightly.
I didn't understand anything in that article, but I'm very excited for the record-breakers and other mathematicians involved. Good job, ya'll.
I understood a fair bit of it but only because I've been studying elliptic curves for a while - Quanta does a good job of straddling the line between informing and educating, but they usually err on the side of presenting results rather than proving or explaining them.
>...but they usually err on the side of presenting results rather than proving or explaining them
And that's exactly what I like about it. They are a news site, hence they present the news. If the news presenters start to chime in you get what you see at CNN / Fox etc, and that's called propaganda, not news. I want news.
you're worried that they'll explain 3rd degree polynomials with a leftist bias?
The overwhelming majority of their publication on organics has an unmistakable bias toward D- sugars ...
I mean, look at all the insane places leftists have shoehorned gender crap into lately. I wouldn't put it past them.
Ah yes, leftists shoehorning gender into checks notes elliptic curve math discussion.
Math is racist: https://ddg.co/math+is+racist, because apparently it has got something called "right answer".
introducing the concept of mathsplaining
I wonder if 3blue1brown could explain this a bit better
If you like videos, there are some excellent ones by Richard Borcherds, in very different style to 3b1b but by a Field's medalist
This is his algebraic geometry playlist. The whole course is directed at graduate level but the first few videos are very accessible https://www.youtube.com/playlist?list=PL8yHsr3EFj53j51FG6wCb...
first thing i did when i read "3rd degree polynomial" was search "elliptic curve 3b1b"
As a typical software engineer, I'm just curious to know if my curve ed25519 key is safe and for how long. :)
I’m not sure how the discovery of new, exotic elliptic curves has security implications on curves used for cyber security.
One thing I've always wondered about elliptic curves is why everything is so centered on degree 3 two variable polynomials.
Aren't there rich structures to be explored for curves of degree >3 ?
Or is 3 really special ?
I think part of the reason why 3 is special is because you get a lot of bang for your buck. Order 3 is a low order polynomial that is relatively easy to analyse, but already gives tremendous mathematical properties.
For example, the points of elliptic curves form groups. The operation of combining the points is described in the article (draw a straight line through two points and mirror in x-axis).
That means that all the theorems that are proven for Groups, are also true for elliptic curves.
But I think there are many more exciting properties
Amateur here (just studying abstract algebra for hobby). I’m also very curious for more reasons.
You can get some higher degree examples (y squared = a degree 4 polynomial, for example), but degree 3 is special. An arbitrary polynomial of degree 4 and higher lack a rich structure (as far as we can tell). You can try to get around it by embedding the curve in a higher dimensional object, but it doesn't get you as far. (This is the idea behind hyperelliptic curve cryptography, for example.)