Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The animated elliptic curve

curves.ulfheim.net

Post reply on HN
Print view View original

51–60 of 62 posts

Re: The animated elliptic curve

#51

Post by xyzzyz »

hutchisonc wrote: post #12
tptacek wrote: post #8

My broken record take on this stuff is that whatever value there is in visualizing elliptic curves, there's more intuition to build just by playing with the curve formulae directly (it's pretty basic math) and seeing how the operations work in code. I don't have the math background to back this up but my understanding of the group rules is that they're --- at least for the application we're using them in --- a little…

For what it’s worth, in the math context (not thinking about applications), the group law is extremely natural. Every variety has an associated group called the Picard group tells you something about geometry of the variety. But for elliptic curves, it turns out there is a bijection between the complex points on the curve and the elements of (the degree 0 subgroup of) its Picard group, so it inherits the group struct…

To expand a little on top of that, you can think of Picard group of a variety as a group of linear combinations of codimension 1 subvarieties. For a 9-dimensional variety, these will be a dimension 8 subvarieties. To connect this huge free group to geometry of the original variety, we introduce certain constraint equations, i.e. we set certain linear combinations to equal to zero. These zero combinations are set to be those combinations that are obtained by intersecting the variety with a (codimension 1) hyperplane: if you take an embedded n-variety, and intersect it with n-1 dimensional plane, you typically get a result that’s a finite union of n-1 subvarieties. One can specify assignment of intersection numbers to each of these varieties, so that eg if a hyperplane intersects a variety “cleanly across” (transversally), the intersection number (and so the coefficient in the constrain equation) is 1, whereas if the intersecting hyperplane is tangent along the intersection, the intersection number will correspond to the degree of tangency (eg. the line y = 0 intersects the parabola y = x^2 at the origin with the intersection number (tangency degree) equal to 2).

Now, if the variety in question is a curve, the codimension 1 subvarieties will be of dimension 0, that is, finite sets of points. Moreover, if the curve is of degree 3, then hyperplanes (lines) will intersect it in exactly 3 points (counting the tangent intersections properly). Thus, we will get a bunch of constraints of the form:

P + Q + R = 0

This makes our huge group of linear combinations into rather simple group of points: take two points, P and Q. Run line across them, take third point of intersection: this is the negative of the sum P + Q. This is the procedure shown on the animations of the OP.

The point of this is that none of this is arbitrary: it’s just a lucky coincidence that happens only in dimension 1 and degree 3. One can introduce group structure on some other complex curves (which will actually look to us like surfaces), but it is not nearly as straightforward.

Re: The animated elliptic curve

#52

Post by turysaz »

syncsynchalt wrote: post #42
geoduck14 wrote: post #41

Earlier quoted context omitted.

I'll agree with GP - this is the best I've seen, too. If I may offer a critique: the final example with Alice and Bob went too fast. I watched it 5 times and I'm a bit lost. I'll rewatch it again later

That’s good feedback. There’s a lot of steps, where should I slow it down? (“All” is an acceptable answer): - Alice computes A - Bob computes B - there’s a 3? second delay - Alice and Bob simultaneously compute the shared secret by multiplying their private key by the others’ public key

I can imagine that play/pause/step buttons could help a lot (for all of the animations), so each reader could "slow it down" manually and take all the time they need.

PS: Great work, thank you! :)

Re: The animated elliptic curve

#53

Post by sbf501 »

syncsynchalt wrote: post #30
sbf501 wrote: post #27

Earlier quoted context omitted.

Great, but that's not an explanation that adds knowledge to the discussion. I mean, Python and JavaScript both have BigInt libraries and are trivial to use. I want to know HOW they work, especially in C, since that's what the majority of popular crypto libraries are written in.

I've cobbled together a few. It's half interesting, and half boring. The boring half is all carry-the-one manual operations that are very much like the addition, multi-digit multiplication, and long division that you learned at a classroom chalkboard. The more interesting is things like modular exponentiation: there's a trick to computing n^e%p for large values, https://en.wikipedia.org/wiki/Modular_exponentiation go…

> It's half interesting, and half boring.

I once emailed Grant from 3b1b and asked if he could explain convolution. Not neural-net convolution, but transfer convolution you learn in linear systems: e.g. f * g where you flip and slide g over f.

His short response: "That's too boring." I was a little miffed. Well, yeah, ECC is boring too, until someone like you makes cool graphics.

Anyway, thanks again!

Re: The animated elliptic curve

#55

Post by syncsynchalt »

turysaz wrote: post #52
syncsynchalt wrote: post #42

Earlier quoted context omitted.

That’s good feedback. There’s a lot of steps, where should I slow it down? (“All” is an acceptable answer): - Alice computes A - Bob computes B - there’s a 3? second delay - Alice and Bob simultaneously compute the shared secret by multiplying their private key by the others’ public key

I can imagine that play/pause/step buttons could help a lot (for all of the animations), so each reader could "slow it down" manually and take all the time they need. PS: Great work, thank you! :)

Ah, hmm. Every animation on the page does have a play/pause _except_ the exchange demo (laugh). I’ll play around with having it pause itself at key points and/or giving it a step button.

Re: The animated elliptic curve

#56

Post by syncsynchalt »

yonrg wrote: post #47
sadjad wrote: post #7

Earlier quoted context omitted.

Great article and great visuals! One very minor missing detail is how the base point P is picked.

That's also where had to scroll up again; where do Alice and Bob know P from? That's pre defined public knowledge, right? It belongs to the curve they use. Many many thanks for this brilliantly depicted explanation! Ot: I also looked up ulfheim after I realized your first name is Michael, not Ulf.

"ulfheim" is an old domain name that I've had for decades; there's a little explanation on my home page but the short version is that it's from an old BBS handle.

Unfortunately a few years ago a racist hate group also started using the name for their own purposes. Today I've started the process of moving all my hosts to a new domain name, xargs.org .

Re: The animated elliptic curve

#57

Post by krapp »

syncsynchalt wrote: post #56
yonrg wrote: post #47

Earlier quoted context omitted.

That's also where had to scroll up again; where do Alice and Bob know P from? That's pre defined public knowledge, right? It belongs to the curve they use. Many many thanks for this brilliantly depicted explanation! Ot: I also looked up ulfheim after I realized your first name is Michael, not Ulf.

"ulfheim" is an old domain name that I've had for decades; there's a little explanation on my home page but the short version is that it's from an old BBS handle. Unfortunately a few years ago a racist hate group also started using the name for their own purposes. Today I've started the process of moving all my hosts to a new domain name, xargs.org .

Yeah, unfortunately Nazis and neo-Nazis have ruined Norse mythology for everyone else.

Re: The animated elliptic curve

#58

Post by max_likelihood »

edflsafoiewq wrote: post #34
max_likelihood wrote: post #32

Earlier quoted context omitted.

Thank you so much for creating this! Under the Curve61 point addition example, I was trying to follow the formula for adding two points: P:(x1, y1) + Q(x2, y2) = R(x3=l^2-x1-x2, y3=l(x1-x3)-y1) where l=(y2-y1)/(x2-x1). I tried to use the example P:(5, 7) + 23P:(2, 24) = (226/9, 2888/7) != 24P:(59, 55) and was wondering where I've gone wrong? Appreciate your response!

You haven't gone wrong, those are equal in F_61. 226 / 9 = (226*34) / (9*34) = 7684 / 306 = 7684 / 1 (since 306 = 1 mod 61) = 59 / 1 (since 7684 = 59 mod 61) I think y3=2888/7 is a typo for 2888/27, which also equals 55 by a similar calculation (1/27 = 52 mod 61).

That was definitely a typo. Thanks for your response!

Re: The animated elliptic curve

#59

Post by max_likelihood »

syncsynchalt wrote: post #38
max_likelihood wrote: post #32

Earlier quoted context omitted.

Thank you so much for creating this! Under the Curve61 point addition example, I was trying to follow the formula for adding two points: P:(x1, y1) + Q(x2, y2) = R(x3=l^2-x1-x2, y3=l(x1-x3)-y1) where l=(y2-y1)/(x2-x1). I tried to use the example P:(5, 7) + 23P:(2, 24) = (226/9, 2888/7) != 24P:(59, 55) and was wondering where I've gone wrong? Appreciate your response!

After a few missteps where I transcribed the vars wrong (laugh) I wrote out the calcs and was able to reach the correct result. Here's my step-by-step process, hope this helps! https://gist.github.com/syncsynchalt/ed02e39ad7adc8580b1086f... Looking at your comment the disconnect seems to be at the division step: when performing a division such as 226/9, look up or calculate the multiplicative inverse for 9 (you can u…

Thanks for explaining and creating the gist! Makes sense now that everything (* / + -) needs to be done modulo 61.
Post reply on HN