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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
