[curves] Isogeny patterns among Edwards curves

[Mike Hamburg]

On Jan 29, 2014, at 6:52 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:

> While counting points on Edwards curves, I've found two obvious,
> useful patterns of isogenies.  I haven't seen them documented
> anywhere, so I'll list them here.  (At the very least, they're useful
> to anyone searching for a new curve.)
> 
> For lack of a better ASCII-friendly notation, I'll use Ed(foo, bar) to
> denote the Edwards curve a*x^2 + y^2 = 1 + d*x^2*y^2 with a=foo,
> d=bar; and Mont(foo, bar) to denote the Montgomery curve B*y^2 = x^3 +
> A*x^2 + x with B=foo, A=bar.
> 
> The first pattern is that Ed(1, d) is isogenous to Ed(-1, d-1) for
> every d that I have tested.

I noticed this too, and I wrote up pretty much exactly what you're thinking.  See http://eprint.iacr.org/2014/027.pdf :-)

> 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?

Cheers,
-- Mike
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140129/328e89fd/attachment.html>