5.1.1 Modular Arithmetic
5.1.1 Modular Arithmetic (Arithmétique modulaire)
Pour des conseils sur l'implémentation efficace et sûre de l'arithmétique modulo p = 2^255 - 19, voir Curve25519 [CURVE25519]. Pour l'inversion modulo p, il est recommandé d'utiliser l'identité x^-1 = x^(p-2) (mod p). L'inversion de zéro ne devrait jamais se produire, car cela exigerait une entrée invalide, qui aurait été détectée auparavant, ou serait une erreur de calcul.
Pour le décodage de point ou la « décompression », des racines carrées modulo p sont nécessaires. On peut les calculer avec l'algorithme de Tonelli-Shanks ou le cas particulier pour p = 5 (mod 8). Pour trouver une racine carrée de a, on calcule d'abord la racine candidate x = a^((p+3)/8) (mod p). Il y a alors trois cas :
-
x^2 = a (mod p). Alors x est une racine carrée.
-
x^2 = -a (mod p). Alors 2^((p-1)/4) * x est une racine carrée.
-
a n'est pas un carré modulo p.