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) となる. 分母は mod 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) を返す.