• 0 Posts
  • 34 Comments
Joined 6 months ago
Cake day: October 26th, 2024
  • azolus@slrpnk.nettoProgramming@programming.dev•What the hell is an elliptic curve?English
    1·
    11 days ago

    Edit: Lemmy somehow converts all my ^ symbols to <sup> and </sup> for whatever reason. My apologies

    In simple terms, an elliptic curve is just the set of points satisfying an elliptic curve equation of form y^2 = x^3 + a*x + b. We say a point is “on the curve” if it satisfies the given equation. The parameters a and b are some “numbers” (often over a finite field—if that doesn’t ring a bell, just ignore it. It’s not important for now) and constant for any specific elliptic curve.

    So let’s say we have the following equation

    y^2 = x^3 + x + 6

    The point (2, 4) would be on the curve, since we can plug in 2 for x and 4 for y and verify that the equality does in fact hold, since we get 4^2 = 16 on the lefthand side and 2^3 + 2 + 6 = 8 + 2 + 6 = 16 on the righthand side.

    Through some mathematical trickery we can also perform operations on the curve, i.e. “add” two points. This is not as straight forward as let’s say standard arithmetic, where you just add numbers as per usual, but we can in fact define an operation that combines two points on the curve to yield another point on the curve cleanly. The process is very ugly when you look at the formula but there is some nice visual intuition for it:

    We have a curve (red) and two points: P and Q. Focus only on the left image for now. We draw a line through both P and Q and see where that line has its third intersection point with the curve. On the left most picture that would be the point R. We take R and mirror it down (imagine putting a mirror along the x-axis, the x-coordinate of R stays the same but the y-coordinate gets flipped). I very expertly drew in that new point in green. And that’s it! That’s our result of adding P and Q.

    The pictures 2, 3 and 4 are a bit weird. In those, we don’t get a third intersection point with the curve. In these special cases we say the result is O—sort of a point at infinity. Don’t think too hard about what that means, it’s just a mathematical trick to deal with the edge-cases. We do this by saying that the result of addition is O if we don’t get a third intersection point with the curve. Adding any point P to O gets you P back. So O is basically our zero for addition.

    This type of “addition” then allows us to perform “calculations” by using the operation defined by the curve. Doing so we can formulate more complicated problems—where finding a solution is very difficult but verifying a solution is easy. This is the basis for their usefulness in cryptography, since we want to be able to encrypt easily but make decrypting without a given key very very difficult.

    Hope that helps!