Closed koba-e964 closed 6 months ago
You're absolutely right that this is true for 2^255 - 19, but it is not true generally (for example, -1 is not square modulo 2^251 - 9). Since this is intended to be a generic procedure, this optimization does not generalize.
My apologies, I was completely mistaken.
The whole point of find_z_ell2
is finding an appropriate value for Z ($u$ in Section 5 of [BHKL13]) for a curve, not a value determined for each invocation of Elligator 2. There is nothing wrong in find_z_ell2
, it returns 2
for GF(2^255 - 19) as expected.
https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/blob/draft-irtf-cfrg-hash-to-curve-14/draft-irtf-cfrg-hash-to-curve.md?plain=1#L4586 -1 is a square in $\mathrm{GF}(2^{255}-19)$, so there is no point in checking F(-ctr) after checking F(ctr) because they have the same result:
2 is a non-square, so it may be worth considering checking ctr and 2*ctr instead: