Posts about encryption, zite development and everything else you wantFollow in NewsfeedFollowing
Today, let's talk about Elliptic Curve arithmetic.
First of all, what is an elliptic curve? If we're working infield, we can say that an elliptic curve is defined by two real numbers and that follows the equation:
This form is called the Weierstrass equation.
We should also mention that this curve should be non-singular, for example:
Ifthe curve is non-singular, and thus it's not an elliptic curve.
Pretend we have two different pointsand both belonging to an elliptic curve. If we draw a line through them, we can see that, in some cases, it intersects the curve in 3 points (including and ), and sometimes in two points ( and themselves), but you'll never have 4 points (or more) on the same line.
What does this mean?
Let's say that, for any, and belonging to the same line, .
Notice that thepoint is not really a point, but rather a special value.
We can now find some interesting properties, for example:
The elliptic curve is symmetric. For example, ifbelongs to the curve, will do as well. Let's define if .
If you draw a line throughand , it won't have any other intersection points. In this case, let's say that .
Sinceand may be the same point, any other would be okay. Instead, let's say that we want such that it is the only other point of intersection. In fact, this means that the line is the tangent. Thus, .
Sincemay be an argument, let's say that it belongs to any line, i.e. it's a neutral element — thus, .
If we combine 5. and 6., we get that.
So, now we understand thatshould be a neutral element to make at least some sense.
So, why did we need this?
If we say thatis the same as a zero in real numbers, we now get an algorithm to get the sum of two points.
Draw a line throughand .
Intersect it with the curve and get.
Moreover, we can notice that all the usual properties apply, i.e.:and .
Instead of using geometrical interpretation which would be difficult to transform into formulas, we'll use the following rule:
Given, we get and , such that .
If, i.e. is not defined, and , it's easy to notice that , and, thus, as well. Notice that the case is handled here as well.
If, and , we want the tangent, thus:
I won't prove this fact here, but you can notice that it gives the same results as the geometrical way.
An elliptic curve is defined the following way:. We can define addition, such that, given two points (or zeroes) and , we can get . This "addition" follows the and properties.
Why would you need this? I'll tell you the next time.