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

|improve this answer|||||
$\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.