Add x-only ecmult_const version with x specified as n/d

[sipa]

Based on #979.

This implements a generalization of Peter Dettman's sqrt-less x-only random-base multiplication algorithm from #262, using the Jacobi symbol algorithm from #979. The generalization is to permit the X coordinate of the base point to be specified as a fraction $n/d$:

To compute the X coordinate of $q \cdot P$, where $x(P) = n/d$:

• Compute $g=n^3 + 7d^3$.
• Let $P' = (ng, g^2, 1)$ (the Jacobian coordinates of $P$ mapped to the isomorphic curve $y^2 = x^3 + 7(dg)^3$).
• Compute the Jacobian coordinates $(X',Y',Z') = q \cdot P'$ on the isomorphic curve.
• Return $X'/(dgZ'^2)$, which is the affine x coordinate on the isomorphic curve $X/Z'^2$ mapped back to secp256k1.

This ability to specify the X coordinate as a fraction is useful in the context of x-only Elligator Swift, which can decode to X coordinates on the curve without inversions this way.

[peterdettman]

Hey @sipa, cool idea. Should that just be sqrt(g) in the second step?

[sipa]

@peterdettman I don't think so.

• x = X / Z^2 = n*g / sqrt(d*g)^2 = n*g / (d*g) = n/d = x
• y = Y / Z^2 = g^2 / sqrt(d*g)^3 = (n^3 + B*d^3)^2 / sqrt(d^3) / (n^3 + B*d^3)^1.5 = sqrt(n^3 + B*d^3) / sqrt(d^3) = sqrt(n^3/d^3 + B) = y

[peterdettman]

OK, well it's late here, so I'll go over it when not so tired. A followup question: is there an assumption that d is square? If not, a better starting point might be (y*d^3)^2 =(x*d^2)^3 + B*d^6 i.e. g = (n.d)^3 + B*d^6, so that this will not be a quadratic twist if d is non-square.

[sipa]

@peterdettman It works for d square or non-square (obviously not for d=0). The reason is that g = y^2*d^3, and thus d*g = y^2*d^4 = (y*d^2)^2, which is always square if n/d is an x coordinate on the curve. In fact, that's how the known_on_curve=0 check works: compute jacobi symbol of d*g.

At least the unit tests here seem to agree that d does not need to be square.

[peterdettman]

Oh I see you meant that (n*g, +- g^2, sqrt(d*g)) is on the original curve, not the one implied in step 1.

[sipa]

Yeah, so just operationally, the algorithm is:

• Input $n$, $d$, $q$
• Compute $g = n^3 + 7d^3$
• Construct affine point $P = (ng, g^2)$ on isomorphic curve
• Compute Jacobian result point $R = (X, Y, Z) = q \cdot P$ on isomorphic curve
• Return $X / (Z^2 d g)$, which is the affine x coordinate on the original curve