• # H1
• ## H2
• ### H3
• _italic_
• **bold**
• ~~strikethrough~~
• - Lists
• 1. Numbered lists
• [References][1]
[1]: Can be used
• ![image alt](img/logo.png)
• Inline code
• pythonprint "Code block"
• > Quotes
• --- Horizontal rule
? Editing: Post:21.body Cancel
Content changed

# Ivanq's Blog

## Posts about encryption, zite development and everything else you want

• leftside: Great! thanks for ur kind work!
• gitcenter: Sorry, something went wrong. Fixed now!
• leftside: All mathematical equations seem to look raw html tags..! ...
• nofish: WebGL under linux can be problematic, here is some tips...

# Title

21 hours ago · 2 min read ·
Body

# Introduction into Elliptic Curve arithmetic

on Apr 28, 2019 · 5 min read

Today, let's talk about Elliptic Curve arithmetic.

## Elliptic curves

First of all, what is an elliptic curve? If we're working in $\R$ field, we can say that an elliptic curve is defined by two real numbers $a$ and $b$ that follows the equation:

$x^2 = y^3 + ax + b$

This form is called the Weierstrass equation.

We should also mention that this curve should be non-singular, for example:

If $a = b = 0$ the curve is non-singular, and thus it's not an elliptic curve.

## Interesting properties of elliptic curves

Pretend we have two different points $P$ and $Q$ 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 $P$ and $Q$), and sometimes in two points ($P$ and $Q$ themselves), but you'll never have 4 points (or more) on the same line.

What does this mean?

Let's say that, for any $P$, $Q$ and $R$ belonging to the same line, $P + Q + R = O$.

Notice that the $O$ point is not really a point, but rather a special value.

We can now find some interesting properties, for example:

1. The elliptic curve is symmetric. For example, if $(x, y)$ belongs to the curve, $(x, -y)$ will do as well. Let's define $-P = (x, -y)$ if $P = (x, y)$.

2. If you draw a line through $P$ and $-P$, it won't have any other intersection points. In this case, let's say that $P + (-P) + O = O$.

3. $\forall P, Q, R: P + Q + R = Q + P + R$

4. $\forall P, Q: (P + Q) + R = P + (Q + R)$

5. Since $Q$ and $R$ may be the same point, any other $P$ would be okay. Instead, let's say that we want such $P$ that it is the only other point of intersection. In fact, this means that the line is the tangent. Thus, $\forall P, Q: P + Q + Q = O \iff PQ \space \text{is a tangent}$.

6. Since $O$ may be an argument, let's say that it belongs to any line, i.e. it's a neutral element — thus, $\forall P, Q: P + Q + O = O$.

7. If we combine 5. and 6., we get that $\forall P: P + P + O = O$.

So, now we understand that $O$ should be a neutral element to make at least some sense.

So, why did we need this?

$P + Q + R = O \implies P + Q = -R$

Woah!

If we say that $O$ is the same as a zero in real numbers, we now get an algorithm to get the sum of two points.

1. Draw a line through $P$ and $Q$.

2. Intersect it with the curve and get $R$.

3. Invert $R$.

Moreover, we can notice that all the usual properties apply, i.e.: $P + Q = Q + P$ and $(P + Q) + R = P + (Q + R)$.

### Algebraic implementation

Instead of using geometrical interpretation which would be difficult to transform into formulas, we'll use the following rule:

Given $x_P, y_P, x_Q, y_Q$, we get $x_R$ and $y_R$, such that $P + Q = R$.

$s = \frac{y_P - y_Q}{x_P - x_Q} \newline x_R = s^2 - x_P - x_Q \newline y_R = -y_P + s(x_P - x_R)$

If $x_P = x_Q$, i.e. $s$ is not defined, and $y_P = -y_Q$, it's easy to notice that $P + Q = O$, and, thus, $R = O$ as well. Notice that the $P = Q = O$ case is handled here as well.

If $x_P = x_Q$, and $y_P = y_Q \neq 0$, we want the tangent, thus:

$s = \frac{3 x_P^2 + a}{y_P + y_Q}$

I won't prove this fact here, but you can notice that it gives the same results as the geometrical way.

## Conclusion

An elliptic curve is defined the following way: $y^2 = x^3 + ax + b$. We can define addition, such that, given two points (or zeroes) $P$ and $Q$, we can get $R$. This "addition" follows the $P + Q = Q + P$ and $(P + Q) + R = P + (Q + R)$ properties.

Why would you need this? I'll tell you the next time.

user_name1 day ago
Body
leftsideon Apr 30, 2019

gitcenter: Sorry, something went wrong. Fixed now!

Great! thanks for ur kind work!

gitcenteron Apr 29, 2019

leftside: All mathematical equations seem to look raw html tags..!what's wrong?

Sorry, something went wrong. Fixed now!

leftsideon Apr 29, 2019