5.2.3 Decoding (Decodifica)

5.2.3 Decoding (Decodifica)

La decodifica di un punto, dato come stringa di 57 ottetti, è un po' più complicata.

1. Prima interpretare la stringa come intero in rappresentazione little-endian. Il bit 455 di questo numero è il bit meno significativo della coordinata x; denotare questo valore con x_0. La coordinata y si recupera semplicemente azzerando tale 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 mod p. Siano 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+1)/4). Si può fare con il seguente accorgimento, usando un'unica elevazione modulare sia per l'inversione di v sia per la radice quadrata:

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

3. Se v * x^2 = u, la coordinata x recuperata è x. Altrimenti non esiste radice quadrata 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).