[curves] Isogeny patterns among Edwards curves

[Samuel Neves]

On 29-01-2014 18:22, Mike Hamburg wrote:
>> The second pattern is that Mont(1, 4*d + 2) is isogenous to Ed(-1,
>> d).  For example:
>>
>> I noticed this pattern while looking for a twist-secure
>> small-parameter Edwards curve over the Curve25519 coordinate field:
>> the first winning curve had a value of d suspiciously similar to
>> (A+2)/4 for one of the curves that Dr. Bernstein considered in the
>> Curve25519 paper.  Further experiments showed that the pattern held
>> for the other two curves considered there, including Curve25519
>> itself.
>
> This is neat, and I didn't know it before you mentioned it on the
> Montgomery thread.  Do you know what the isogeny is?  Is it simple,
> and does it interact nicely with point compression?  Is it a 2-isogeny
> or a 4-isogeny?
>

It can be derived from [1]. Composing E_{1, d} -> E_{-1, d-1} with E_d
-> E_{1-1/d} (Section 3), and using the identity A = 4/(1 - d) - 2, one
gets the isogeny E_{-1, d} -> M_{4*d + 2}. From what I can tell this is
a 4-isogeny.

[1] http://eprint.iacr.org/2011/135