[curves] Isogeny patterns among Edwards curves

[Robert Ransom]

On 1/30/14, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On 1/30/14, Mike Hamburg <mike at shiftleft.org> wrote:
>
>> This issue of decompression to Edwards remains, and this is not cheap: it
>> costs 2 square roots instead of 1, or at least a square root and a
>> Legendre
>> symbol check (even when p==1 mod 4: the criterion is that d has to be
>> nonsquare).  I'm looking for a way to fix this now, but I'm not sure
>> there
>> is one.
>
> Do you mean one square root in the quadratic extension field?
>
> (I see (sqrt(d)*x + Y)^2 = 1 + a*(x*Y)^2 + 2*sqrt(d)*x*Y (where Y=1/y)
> as a way to recover x and Y.)

I see now.  You must have solved for x in terms of t^2 (where t =
x/y), and that produces a quadratic equation in x^2.  (That should be
faster than mucking about with the extension field.)

*But*, you can use x^2 and t to finish evaluating the isogeny into
Montgomery form!  (y^2 = x/t^2)


Robert Ransom