5.2.3 Decoding

Decoding a point, given as a 57-octet string, is a little more complicated.

First, interpret the string as an integer in little-endian representation. Bit 455 of this number is the least significant bit of the x-coordinate, and denote this value x_0. The y-coordinate is recovered simply by clearing this bit. If the resulting value is >= p, decoding fails.
To recover the x-coordinate, the curve equation implies x^2 = (y^2 - 1) / (d y^2 - 1) (mod p). The denominator is always non-zero mod p. Let u = y^2 - 1 and v = d y^2 - 1. To compute the square root of (u/v), the first step is to compute the candidate root x = (u/v)^((p+1)/4). This can be done using the following trick, to use a single modular powering for both the inversion of v and the square root:

                         (p+1)/4    3            (p-3)/4
                x = (u/v)        = u  v (u^5 v^3)         (mod p)

If v * x^2 = u, the recovered x-coordinate is x. Otherwise, no square root exists, and the decoding fails.
Finally, use the x_0 bit to select the right square root. If x = 0, and x_0 = 1, decoding fails. Otherwise, if x_0 != x mod 2, set x <- p - x. Return the decoded point (x,y).

5.2.3 Decoding​