[curves] Isogeny patterns among Edwards curves
Michael Hamburg
mike at shiftleft.org
Wed Jan 29 18:56:45 PST 2014
On Jan 29, 2014, at 11:10 AM, Samuel Neves <sneves at dei.uc.pt> wrote:
> 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
Apparently the 4-isogeny is
(x,y) -> (y^2/x^2, y(x^2+y^2-2)/x^3)
from Ed(d): x^2 + y^2 = 1 + d x^2 y^2
to Mont(2-4d) : y^2 = x(x^2 + (2-4d)x + 1)
in which (A-2)/4 = -d, or (A+2)/4 = 1-d.
Cheers,
— Mike
More information about the Curves
mailing list