[curves] Montgomery/Edwards curve generation

[Mike Hamburg]

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 <conradoplg at 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 at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves