5.2.3 Decoding (解码)
5.2.3 Decoding (解码)
对给定的 57 个八位组串进行点解码要更复杂一些。
-
首先将该串按小端表示解释为一个整数。该数的第 455 位是 x 坐标的最低有效位, 记此值为 x_0。通过清除该位即可恢复 y 坐标。若所得值 >= p, 则解码失败。
-
为恢复 x 坐标, 由曲线方程可得 x^2 = (y^2 - 1) / (d y^2 - 1) (mod p)。分母在模 p 下恒非零。令 u = y^2 - 1, v = d y^2 - 1。要计算 (u/v) 的平方根, 第一步是计算候选根 x = (u/v)^((p+1)/4)。可用下述技巧在一次模幂中同时完成 v 的求逆与平方根:
(p+1)/4 3 (p-3)/4
x = (u/v) = u v (u^5 v^3) (mod p)
-
若 v * x^2 = u, 则所恢复的 x 坐标为 x。否则不存在平方根, 解码失败。
-
最后用 x_0 位选取正确的平方根。若 x = 0 且 x_0 = 1, 解码失败。否则, 若 x_0 != x mod 2, 则令
x <- p - x。返回解码得到的点 (x,y)。