8
$\begingroup$

The equation of an Edwards curve is $x^2 + y^2 = 1 + d x^2 y^2 \,$

The addition formula is $(x_1,y_1) + (x_2,y_2) = \left( \frac{x_1 y_2 + x_2 y_1}{1 + dx_1 x_2 y_1 y_2}, \frac{y_1 y_2 - x_1 x_2}{1 - dx_1 x_2 y_1 y_2} \right) \,$

Why can't you divide by zero when you have a non-square d?

What is the intuitive explanation that $dx_1 x_2 y_1 y_2$ can't be equal to ± 1 when d is a non-square? Because I don't see why you can't have $x_1 x_2 y_1 y_2 = ± \frac{1}{d}$

$\endgroup$
7
$\begingroup$

Claim:

Both denominators can never be zero if $d$ is not square in $K$.

Proof:

Let $(x_1, y_1)$ and $(x_2, y_2)$ be on the curve, i.e., $x_i^2+y_i^2=1+dx_i^2y_i^2$. Write $\epsilon=dx_1x_2y_1y_2 \neq 0$ and suppose $\epsilon \in \{-1,1\}$. Then $x_1, x_2, y_1, y_2 \neq 0$ and

\begin{equation} \begin{split} dx_1^2y_1^2(x_2^2+y_2^2) & = dx_1^2y_1^2(1+dx_2^2y_2^2) \\ & = dx_1^2y_1^2 + d^2x_1^2y_1^2x_2^2y_2^2 \\ & = dx_1^2y_1^2 + \epsilon^2 \\ & = 1+dx_1^2y_1^2 \\ & = x_1^2 + y_1^2 \end{split} \end{equation}

Now we need to show that $\epsilon = dx_1x_2y_1y_2 = \pm1$ implies $d$ is a square. For now we have $dx_1^2y_1^2(x_2^2+y_2^2)=x_1^2+y_1^2$. It follows that

\begin{equation} \begin{split} (x_1+\epsilon y_1)^2 &= x_1^2+y_1^2+2\epsilon x_1y_1 \\ & = dx_1^2y_1^2(x_2^2+y_2^2)+2x_1y_1dx_1x_2y_1y_2 \\ &= dx_1^2y_1^2(x_2^2+2x_2y_2+y_2^2) \\ &=dx_1^2y_1^2(x_2+y_2)^2 \end{split} \end{equation}

$x_2+y_2 \neq 0 \rightarrow d=\left(\frac{(x_1+\epsilon y_1)}{x_1y_1(x_2+y_2)}\right)^2 $

$x_2-y_2 \neq 0 \rightarrow d=\left(\frac{(x_1-\epsilon y_1)}{x_1y_1(x_2-y_2)}\right)^2 $

Now if $x_2+y_2 = 0$ and $x_2-y_2=0$, then it follows that $x_2=y_2=0 \rightarrow$ contradiction to the statement we made above ($x_1,x_2,y_1,y_2 \neq 0)$.

$\endgroup$
2
$\begingroup$

The addition law on the elliptic curves maps pairs of points over the field $\Bbbk$ to a new point over $\Bbbk$. To understand why there can be no division by zero, one needs to understand the completion of the affine curve $x^2 + y^2 = 1 + dx^2 y^2$ which is only a part of the full Edwards curve, since an elliptic curve is never affine. The true Edwards curve is a curve in $\mathbb P^1 \times \mathbb P^1$, which is a space of pairs of pairs of points $((x,z),(y,w))$ with two such pairs identified if they differ by a multiplication by a pair of nonzero numbers: $$((x,z),(y,w)) \sim ((\lambda x,\lambda z),(\mu y,\mu w)),\ \lambda,\mu\in \Bbbk^*$$

None of the pairs $(x,z)$ or $(y,w)$ can equal $(0,0)$. The equation in the projective coordinates looks as follows: $$x^2 w^2 + y^2 z^2 = z^2 w^2 + d x^2 y^2$$ You get the affine patch by setting $w=z=1$. Now, one can get "points at infinity" by considering the case when $w=0$ or $z=0$. If $w=0$: $$y^2 (z^2 - dx^2) = 0$$ So either $y=0$ (which is impossible since $(y,w)=(0,0)$ is forbidden) or $d=(z/x)^2$, the latter being impossible if $d$ is not a square in $\Bbbk$. Similarly, for $z=0$ there are also no points at infinity.

So if $d$ is not a square in $\Bbbk$, then there are no points at infinity at all. A zero in the denominator of the addition law would produce exactly such a point, thus zeroes in the denominators are also impossible.

One could also ask if there could be a simultaneous zero of both the numerator and the denominator in the addition law, and the answer is also no for the same reason. Remember that the group law on the elliptic curve is defined algebraically, not analytically, so there can be no "removal of indeterminacies 0/0". A simultaneous zero in the numerator and denominator would mean a point on the curve of the form $((x,z),(0,0))$ (or vice versa), which are excluded by definition.

$\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.