ElligatorSwift + integrated x-only DH

[sipa]

Builds on top of #979, #1118. Replaces #982.

This implements encoding of curve points using the ElligatorSwift algorithm (https://eprint.iacr.org/2022/759), with two changes:

• Inputs (u,t) where u=0, t=0, or u^2+t^3+7=0, are remapped to other finite points, rather than outputting infinity.
• The sign of Y is encoded in (u,t) itself rather than needing a separate bit.

In addition, it adds an integrated x-only Diffie-Hellman implementation on top of it, exploiting the fact that no Y coordinate needs to be decoded due to:

• ElligatorSwift being able to operate on just X coordinates
• #262's trick avoiding the need to compute a Y coordinate in X-only DH.

This is significantly faster than the ElligatorSquare code in #982.

TODO:

• [x] Tests comparing with vectors generated by paper author's code
• [ ] Valgrind ctime checks

[sipa]

@real-or-random Re posdivsteps see #979 which this PR is based on.

[paulmillr]

Looks awesome! Wanted to clarify this bit, for implementors of EllSwift in other languages / for standardization purpose.

Inputs (u,t) where u=0, t=0, or u^2+t^3+7=0, are remapped to other finite points, rather than outputting infinity.

To which points exactly? It's not immediately obvious from the code.

[sipa]

@paulmillr They are remapped as follows:

• If t=0, set t=1 instead
• If u=0, set u=1 instead
• If u^2+t^3+B=0, set t=2*t instead
• Run the normal algorithm

(for applicable odd-ordered curves with A=0, this covers all otherwise unmapped points, but this remapping doesn't work for every ellswift-compatible curve).

[sipa]

Added test vectors.

[sipa]

I've made a number of improvements:

• Addressed comments so far
• Added test vectors that are verified against the paper author's Sage code (https://github.com/Jchavezsaab/SwiftEC).
• Documented the algorithms line-by-line
• Renamed functions to better match the paper's names.
• Split up the commits
• A few small performance optimizations
• Factored out helper functions for checking if an X coordinate is on the curve (directly, and when given as a fraction).

I think it's ready for more review.