Thanks Mike! That was the final piece of the puzzle. Cheers,
Conrado On Tue, Mar 20, 2018 at 4:50 PM, Mike Hamburg <m...@shiftleft.org> wrote: > Hi Conrado, > > This looks right to me. Note that if a and d are both square or both > nonsquare, then ad = (A^2-4) is square. In that case, you can solve the > quadratic x^2+Ax+1=0, so there are additional points on the Montgomery > curve where y=0. These points have order 2, and so would be at infinity on > the isomorphic Edwards curve. Therefore that Edwards curve can’t be > complete. However, there might be an isogenous complete Edwards curve, > using the same family of isogenies as Ed448-Goldilocks. > > Cheers, > — Mike > > Sent from my phone. Please excuse brevity and typos. > > > On Mar 20, 2018, at 12:35, Conrado P. L. Gouvêa <conrado...@gmail.com> > wrote: > > > > Hi, > > > > I've been studying the process used to generate Montgomery and Edwards > curves. > > > > Generating Montgomery seems fairly straightforward. Pick B = 1 for speed > and select a suitable A that generates a curve / twist curve with > near-prime order. Only values such that (A-2) % 4 == 0 are considered, also > for speed. > > > > Now suppose you want to create an Edwards curve E(a,d) from a certain > Montgomery M(A,B=1) curve found. The default mapping is to set a = (A + 2) > and d = (A - 2). > > The first problem is: from what I understand, in order for the formulas > to be complete, "a" needs to be square and "d" needs to be nonsquare. > > The second problem is: "a" is usually 1 or -1 for speed reasons. > > > > Reading about it, I've kind of deduced that the following is the > approach taken, but I'd like to verify if this is correct. > > > > If "a" is square and "d" nonsquare, you're almost done. Use the mapping > (x', y') -> (x*sqrt(a), y) and get the curve E(1,d/a) which is isomorphic > (birationally equivalent?) to E(a,d). If your prime is 1 modulo 4 then -1 > is square, so you can target "a" == -1 which is faster. Use the mapping > (x', y') -> (-x*(sqrt(a)/sqrt(-1)), y) and get the curve E(-1, -d/a). > > (This is how edwards25519 was generated) > > > > If "a" is nonsquare and "d" square, you can use the mapping (x', y') -> > (x, 1/y) and get the curve E(d, a). Then follow the previous procedure to > get a new "a" = 1 or "a" = -1. > > (This is how the second curve in the "Curve448" section of RFC 7748 was > generated) > > > > Now if "a" and "d" are both square or nonsquare, it seems you can't do > anything, though I haven't seen this explicitly mentioned anywhere... > > > > Is this reasoning right? > > > > Thanks! > > > > Conrado > > > > _______________________________________________ > > Curves mailing list > > Curves@moderncrypto.org > > https://moderncrypto.org/mailman/listinfo/curves > >
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves