6
$\begingroup$

According to the paper "Faster addition and doubling on elliptic curves" by Bernstein and Lange, the Montgomery curve (Curve25519) $$v^{2}=u^{3}+486662\cdot u^{2}+u$$ is birationally equivalent to the Edwards curve (Ed25519) $$x^{2}+y^{2}=1+(121665/121666)\cdot x^{2}y^{2}.$$The paper says that the transformation is easy and can be done with$$v=\sqrt{486662}\cdot u/x$$ $$u=(1+y)/(1-y).$$ However, when I try to do this transformation I do not obtain the Edwards curve, but I get $$(2+d)x^{2}+dy^{2}=d+(d-2)x^{2}y^{2}$$ with $d=486662$.

So I wonder how, starting from Curve25519, I can get to $e=121665/121666$ and $$x^{2}+y^{2}=1+e\cdot x^{2}y^{2}?$$ Thanks!


The detailed transformation:

Transformation

$\endgroup$
  • $\begingroup$ maybe this helps (somehow): $(d-2)/ 4=121665$ and $(d+2)/4=121666$, meaning $(d-2)/(d+2)=121665/121666$. $\endgroup$ – SEJPM Jul 16 '15 at 19:15
  • $\begingroup$ things would work out perfectly if "your" $dy^2$ could be replaced by $(d+2)y^2$ and "your" standalone $d$ by $d+2$... Did you verify your transformations are correct? $\endgroup$ – SEJPM Jul 16 '15 at 19:18
  • $\begingroup$ @SEJPM: Thanks for your hints! I checked the transform twice, so I think it is correct. Maybe one has to divide by $d$ and then maybe the birational equivalence allows to replace $x^2$ by $x^2d/(d+2)$? The factor 4 is then just a simplification. $\endgroup$ – Chris Jul 16 '15 at 19:33
  • $\begingroup$ @SEJPM Seems you´ve got an acceptable answer right there around the corner… ;) $\endgroup$ – e-sushi Jul 16 '15 at 19:40
  • 1
    $\begingroup$ I think I've just got it. According to this presentation you're allowed to linearly transform the coordinates (and some other things) if you want to keep birational equivalence. So the change you proposed seems to be allowed. $\endgroup$ – SEJPM Jul 16 '15 at 21:00
8
$\begingroup$

First off, your equation is correct and there seems to be no calculation mistake.

To understand on how to get from $$(2+d)x^{2}+dy^{2}=d+(d-2)x^{2}y^{2}$$ to $$x^{2}+y^{2}=1+e\cdot x^{2}y^{2}$$ one first needs to observe that $e=(d-2)/(d+2)=121665/121666$ holds.

The next step is to consider: "What operations are actually allowed with birational equivalence?". According to this presentation on a similar topic, linear transformations in the coordinates don't break the birational equivalence as do simple equivalence transformations (the ones having takens us here).

So the substitution $x^2:=x^2\cdot d/(d+2)$ is allowed. If you now perform the substitution, you'll observe $$dx^{2}+dy^{2}=d+d(d-2)/(d+2)x^{2}y^{2}$$ and dividing by $d$ yields the desired equation.

$\endgroup$
  • $\begingroup$ answer 101, I hope it's a good 101 :) $\endgroup$ – SEJPM Jul 16 '15 at 21:32
  • $\begingroup$ I have a good feeling with this answer. Thanks again! :) $\endgroup$ – Chris Jul 16 '15 at 21:43

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.