Decoding

Decoding to a point works as follows where $a$ and $d$ are the curve parameters as described here.

1. Decode s_bytes to a field element $s$. We interpret these bytes as unsigned little-endian bytes. We check if the length has 32 bytes, where the top 3 bits of the last byte are 0. The 32 bytes are verified to be canonical, and rejected if not (if the input is already a field element in the circuit case, skip this step).

2. Check that $s$ is nonnegative, or reject (sign check 1).

3. $u_1\leftarrow 1+a{s}^2$.

4. $u_2\leftarrow u_1^2-4d{s}^2$.

5. (was_square, v) = sqrt_ratio_zeta(1, u_2 * u_1^2), rejecting if was_square is false.

6. $v\leftarrow -v$ if $2s{u}_{1}v$ is negative (sign check 2)¹.

7. $(x,y)\leftarrow (2s{v}^2{u}_1{u}_2,(1-a{s}^2)v{u}_1)$.

The resulting coordinates are the affine Edwards coordinates of an internal representative of the group element.