5.1.1 Modular Arithmetic (模运算)
5.1.1 Modular Arithmetic (模运算)
关于如何高效且安全地实现模 p = 2^255 - 19 的算术, 见 Curve25519 [CURVE25519]. 关于模 p 求逆, 建议使用恒等式 x^-1 = x^(p-2) (mod p). 对零求逆不应发生, 因为那需要无效输入 (此前应已检测) 或计算错误.
对点做 decoding (解码) 或 "decompression (解压缩)" 时, 需要模 p 的平方根. 可用 Tonelli-Shanks 算法或 p = 5 (mod 8) 时的特例. 为求 a 的平方根, 先计算候选根 x = a^((p+3)/8) (mod p). 然后分三种情况:
-
x^2 = a (mod p). 则 x 是一个平方根.
-
x^2 = -a (mod p). 则 2^((p-1)/4) * x 是一个平方根.
-
a 在模 p 下不是平方.