<div dir="ltr">Hi,<div><br></div><div>I've been studying the process used to generate Montgomery and Edwards curves.</div><div><br></div><div>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.</div><div><br></div><div>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).</div><div>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.</div><div>The second problem is: "a" is usually 1 or -1 for speed reasons.</div><div><br></div><div>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.</div><div><br></div><div>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).</div><div>(This is how edwards25519 was generated)</div><div><br></div><div>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.</div><div>(This is how the second curve in the "Curve448" section of RFC 7748 was generated)</div><div><br></div><div>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...</div><div><br></div><div>Is this reasoning right?</div><div><br></div><div>Thanks!</div><div><br></div><div><div><div class="gmail_signature">Conrado</div></div><div class="gmail_signature"><br></div>
</div></div>