5.1.3 Decoding (Decodifica)

5.1.3 Decoding (Decodifica)

Decodificare un punto, dato come stringa di 32 ottetti, è un po' più complicato.

1. Prima, interpretare la stringa come intero in rappresentazione little-endian. Il bit 255 di questo numero è il bit meno significativo della coordinata x; denotare questo valore x_0. La coordinata y si recupera semplicemente azzerando questo bit. Se il valore risultante è >= p, la decodifica fallisce.

2. Per recuperare la coordinata x, l'equazione della curva implica x^2 = (y^2 - 1) / (d y^2 + 1) (mod p). Il denominatore è sempre non nullo modulo p. Sia u = y^2 - 1 e v = d y^2 + 1. Per calcolare la radice quadrata di (u/v), il primo passo è calcolare la radice candidata x = (u/v)^((p+3)/8). Si può fare con il seguente trucco, usando un'unica elevazione modulare sia per l'inverso di v sia per la radice quadrata:

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

3. Di nuovo, ci sono tre casi:

   1. Se v x^2 = u (mod p), x è una radice quadrata.

   2. Se v x^2 = -u (mod p), porre x <-- x * 2^((p-1)/4), che è una radice quadrata.

   3. Altrimenti, non esiste radice quadrata modulo p, e la decodifica fallisce.

4. Infine, usare il bit x_0 per selezionare la radice quadrata corretta. Se x = 0 e x_0 = 1, la decodifica fallisce. Altrimenti, se x_0 != x mod 2, porre x <-- p - x. Restituire il punto decodificato (x,y).