[curves] Isogeny patterns among Edwards curves

[Robert Ransom]

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.  For example:

? setup_field_pnl(206)
q = 2^206 + (-5)
minimal_nonsquare = Mod(-1, q)
? show_curve_info(setup_edwards_curve(1, 42))
twisted Edwards curve, a=1, d=42: trace of Frobenius =
14068830327124887607521427000336
twisted Edwards curve, a=1, d=42: j =
-19775347852011252189935586830226891134702416204702366104028191
? show_curve_info(setup_edwards_curve(-1, 41))
twisted Edwards curve, a=-1, d=41: trace of Frobenius =
14068830327124887607521427000336
twisted Edwards curve, a=-1, d=41: j = -85015732/7973721

? setup_field_pnl(190)
q = 2^190 + (-11)
minimal_nonsquare = Mod(2, q)
? show_curve_info(setup_edwards_curve(1, 42))
twisted Edwards curve, a=1, d=42: trace of Frobenius =
23826435152901951766804494722
twisted Edwards curve, a=1, d=42: j =
-29780660969891434142119553805572537670037009899273230687
? show_curve_info(setup_edwards_curve(-1, 41))
twisted Edwards curve, a=-1, d=41: trace of Frobenius =
23826435152901951766804494722
twisted Edwards curve, a=-1, d=41: j = -85015732/7973721

Once I noticed that repeated traces were occurring in this pattern, I
modified my curve-finding script to use it to reduce the number of
curves that I applied the SEA algorithm to.


The second pattern is that Mont(1, 4*d + 2) is isogenous to Ed(-1,
d).  For example:

? setup_field_pnl(206)
q = 2^206 + (-5)
minimal_nonsquare = Mod(-1, q)
? show_curve_info(setup_montgomery_curve(1, 4*42 + 2))
Montgomery curve, B=1, A=170: trace of Frobenius =
-16621236410369812189513106627620
Montgomery curve, B=1, A=170: j =
-21468549906910806959178550035441623075113905777403766002269495
? show_curve_info(setup_edwards_curve(1, -42))
twisted Edwards curve, a=1, d=-42: trace of Frobenius =
-16621236410369812189513106627620
twisted Edwards curve, a=1, d=-42: j = -1630532233/143589642

? setup_field_pnl(190)
q = 2^190 + (-11)
minimal_nonsquare = Mod(2, q)
? show_curve_info(setup_montgomery_curve(1, 4*42 + 2))
Montgomery curve, B=1, A=170: trace of Frobenius = 10602238031348418681656683042
Montgomery curve, B=1, A=170: j =
569144744833648380441921660049975291050255096376033058898
? show_curve_info(setup_edwards_curve(1, -42))
twisted Edwards curve, a=1, d=-42: trace of Frobenius =
10602238031348418681656683042
twisted Edwards curve, a=1, d=-42: j = -1630532233/143589642

? setup_field_pnl(255)
q = 2^255 + (-19)
minimal_nonsquare = Mod(2, q)
? show_curve_info(setup_montgomery_curve(1, 4*121665 + 2))
Montgomery curve, B=1, A=486662: trace of Frobenius =
-221938542218978828286815502327069187962
Montgomery curve, B=1, A=486662: j =
-8402984886491173945284813825263643018331137036053042434342051324546836720331
? show_curve_info(setup_edwards_curve(1, -121665))
twisted Edwards curve, a=1, d=-121665: trace of Frobenius =
-221938542218978828286815502327069187962
twisted Edwards curve, a=1, d=-121665: j =
-11383460873643625840482993965353531234491853591306867391444798534299255498119

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.


The j-invariants show that these isogenies are not isomorphisms.


The most interesting use of one of these isogenies is probably that
Ed(1, (2169/2171)^2) is isogenous to Ed(-1, (2169/2171)^2 - 1) over
GF(2^414-17); the former has efficient parameters for use with the
formulas listed on
<http://hyperelliptic.org/EFD/g1p/auto-edwards-yzsquared.html>, while
the latter is isomorphic to Ed(1, -1/((2169/2171)^2 - 1)), which has a
complete addition law.  Both are twist-secure.


Robert Ransom