5.1.1 Modular Arithmetic (Aritmetica modulare)
5.1.1 Modular Arithmetic (Aritmetica modulare)
Per consigli su come implementare in modo efficiente e sicuro l'aritmetica modulo p = 2^255 - 19, vedere Curve25519 [CURVE25519]. Per l'inversione modulo p, si raccomanda di usare l'identità x^-1 = x^(p-2) (mod p). Invertire zero non dovrebbe mai accadere, poiché richiederebbe input non validi, che sarebbero stati rilevati in precedenza, oppure sarebbe un errore di calcolo.
Per la decodifica del punto o la "decompressione", servono radici quadrate modulo p. Si possono calcolare con l'algoritmo di Tonelli-Shanks o il caso speciale per p = 5 (mod 8). Per trovare una radice quadrata di a, si calcola prima la radice candidata x = a^((p+3)/8) (mod p). Poi ci sono tre casi:
-
x^2 = a (mod p). Allora x è una radice quadrata.
-
x^2 = -a (mod p). Allora 2^((p-1)/4) * x è una radice quadrata.
-
a non è un quadrato modulo p.