5.1.1 Modular Arithmetic
5.1.1 Modular Arithmetic
For advice on how to implement arithmetic modulo p = 2^255 - 19 efficiently and securely, see Curve25519 [CURVE25519]. For inversion modulo p, it is recommended to use the identity x^-1 = x^(p-2) (mod p). Inverting zero should never happen, as it would require invalid input, which would have been detected before, or would be a calculation error.
For point decoding or "decompression", square roots modulo p are needed. They can be computed using the Tonelli-Shanks algorithm or the special case for p = 5 (mod 8). To find a square root of a, first compute the candidate root x = a^((p+3)/8) (mod p). Then there are three cases:
-
x^2 = a (mod p). Then x is a square root.
-
x^2 = -a (mod p). Then 2^((p-1)/4) * x is a square root.
-
a is not a square modulo p.