1
$\begingroup$

I've been troubled by this, given any random number as the number of times we'll multiply a point by itself, will we always be guaranteed to land on the curve again? Is there a case where we'll have a miss?

Also, is the question to above not always true unless we are in finite fields defined by specific curves? Is this part of the reason why we need to choose specific curves?

$\endgroup$
  • $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$ – fkraiem Sep 12 '17 at 0:11
3
$\begingroup$

Adding two points on a curve following the addition law will always give another point on the curve. That's part of what it means for the curve to form a group.

The addition law is defined relative to a particular curve and a particular field. For example, consider the field $\mathbb F_3$, i.e. the integers $\{0, 1, 2\}$ with arithmetic—addition and multiplication—performed modulo 3, and consider the curve $$E/\mathbb F_3 : x^2 + y^2 = 1 + 2 x^2 y^2.$$ The point $(1, 0)$ (i.e., $x = 1, y = 0$) is on this curve, which you can check by a simple calculation. The point $(2, 0)$, however, is not. (Exercise: List, for every possible $x, y \in \mathbb F_3$, whether $(x, y)$ is on the curve. There are only nine of them!) The addition law $$(x_0, y_0) + (x_1, y_1) = \left(\frac{x_0 y_1 + x_1 y_0}{1 + d x_0 x_1 y_0 y_1}, \frac{y_0 y_1 - x_0 x_1}{1 - d x_0 x_1 y_0 y_1}\right)$$ always gives another point on the curve. For example, $(2, 1)$ is also on the curve, and $$(1, 0) + (2, 1) = \left(\frac{1 + 0}{1 + 0}, \frac{0 - 2}{1 - 0}\right) = \left(1, \frac{-2}{1}\right) = (1, 1),$$ which you can check by another simple calculation.

That addition law always works for the points $(x, y)$ on $E$ for $x, y \in \mathbb F_3$, but does not always work for every curve or every field. For example, it does not work for $$E/\mathbb F_7 : x^2 + y^2 = 1 + 4 x^2 y^2$$ because $4 = 2\cdot 2$ is a quadratic residue in $\mathbb F_7$. (Try it with $(1, 5)$ and $(4, 5)$—you'll get a denominator which is a multiple of 7, which is equivalent to zero in $\mathbb F_7$, which you can't divide by.) Not every curve can even be written in this form, which is called Edwards form; for example, curves of prime order, such as NIST P-256, have no Edwards form. Other forms of curves have different addition laws, which work on different subsets of points and in different cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.