5.2.3 Decoding (Décodage)

Le décodage d'un point, donné comme une chaîne de 57 octets, est un peu plus compliqué.

D'abord, interpréter la chaîne comme un entier en représentation little-endian. Le bit 455 de ce nombre est le bit de poids faible de la coordonnée x ; noter cette valeur x_0. La coordonnée y est récupérée simplement en effaçant ce bit. Si la valeur résultante est >= p, le décodage échoue.
Pour récupérer la coordonnée x, l'équation de la courbe implique x^2 = (y^2 - 1) / (d y^2 - 1) (mod p). Le dénominateur est toujours non nul modulo p. Soit u = y^2 - 1 et v = d y^2 - 1. Pour calculer la racine carrée de (u/v), la première étape est de calculer la racine candidate x = (u/v)^((p+1)/4). On peut le faire avec l'astuce suivante, pour n'utiliser qu'une seule exponentiation modulaire à la fois pour l'inversion de v et la racine carrée :

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

Si v * x^2 = u, la coordonnée x récupérée est x. Sinon, aucune racine carrée n'existe et le décodage échoue.
Enfin, utiliser le bit x_0 pour choisir la bonne racine carrée. Si x = 0 et x_0 = 1, le décodage échoue. Sinon, si x_0 != x mod 2, poser x <- p - x. Retourner le point décodé (x,y).

5.2.3 Decoding (Décodage)​