5.1.3 Decoding

5.1.3 Decoding (Décodage)

Décoder un point, donné comme une chaîne de 32 octets, est un peu plus compliqué.

1. D'abord, interpréter la chaîne comme un entier en représentation little-endian. Le bit 255 de ce nombre est le bit le moins significatif de la coordonnée x ; noter cette valeur x_0. La coordonnée y se récupère simplement en effaçant ce bit. Si la valeur résultante est >= p, le décodage échoue.

2. 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+3)/8). On peut le faire avec l'astuce suivante, en une seule exponentiation modulaire pour l'inversion de v et la racine carrée :

                 (p+3)/8      3        (p-5)/8
        x = (u/v)        = u v  (u v^7)         (mod p)

3. Encore une fois, il y a trois cas :

   1. Si v x^2 = u (mod p), x est une racine carrée.

   2. Si v x^2 = -u (mod p), poser x <-- x * 2^((p-1)/4), ce qui est une racine carrée.

   3. Sinon, aucune racine carrée n'existe modulo p, et le décodage échoue.

4. 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).