On Fri, January 31, 2014 15:50, Mike Hamburg wrote: > > On Jan 31, 2014, at 2:13 AM, Paulo S. L. M. Barreto <[email protected]> > wrote: > >> On Fri Jan 31 00:07:44 PST 2014, Mike Hamburg wrote: >> >>> We could start with x^2 + y^2 = 1 - 14666 x^2 y^2 mod 2^192-2^64-1. >>> The isogenous curve y^2 = x^3 + 58666*x^2 + x is isomorphic to >>> y^2 = x^3 - 3*x + >>> 6047900113480193987160910265022055632294672911518856488260. >> >> I think we discussed this one in private already. Let u := sqrt(-d). Then >> 2*(u >> - 1)/(u + 1) is not a square, and the Elligator injective map is undefined. > > We did discuss this, and I pointed out that Elligator 2 is still defined via > the isomorphic Montgomery curve -- and, in fact, for all curves with even > order over a large-characteristic field, except with j=1728. Elligator 2 is > easier to implement than Elligator 1, even including the isomorphism, and it's > just as fast, and it doesn't have any more exceptional points than Elligator > 1.
My bad. I only now noticed that Elligator 1 has 2 exceptional points! So, there are situations (e.g. when p = 5 mod 8) when Elligator 2 has no exceptional point, and when it does, either Elligator 1 is not defined or else both have exactly 2 exceptional points (which, in the most straightforward setting, are precisely the same, i.e. +-1). Nice! > This is a large part of why I'm less than happy with the Brazil curves. They > are designed around this idea that comes from the structure of the Elligator > paper: use Elligator 1 for Edwards curves with p=3 mod 4 (which constrains > your choice of d), and use Elligator 2 with Montgomery curves with p=5 mod 8. > This isn't actually a good design pattern; it's there because Elligator and > Curve1174 were already posted to ePrint before we added Elligator 2. The > actual takeaway is, in my opinion, that you can and should use Elligator 2 for > either curve shape over either field shape, with any d unless j=1728. You convinced me. If you convince Diego as well, we'll have fun redesigning the curve-finding script ;-) (actually I wasn't quite happy with them either, since they don't adopt the more efficient (-1)-twist for Edwards curves) Cheers, Paulo. _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
