アルゴリズムとかオーダーとか

仕事で勉強したことなどをまとめてます

secp256k-1には整数解は存在しないことの証明

証明 数学

久しぶりのブログ投稿になります。こんにちは。今回はsecp256k-1であるy^2=x^3+7に整数解は存在しないことの証明を行いたいと思います。

元々はgemとC Libraryで書かれたsecp256k-1のライブラリが返す加算結果が違っていて、どっちのライブラリが正しい値かを手計算でも検算できそうな整数解となる点はどこかという話が発端でした。


この話題のなかで、「secp256k-1 integer」などでググったところタイトルの通り、整数解は存在しないというhomeworkを見つけました。今回ではこのhomeworkの回答をみながら自分なりに証明をしていきたいと思います。

1. xが偶数の時の証明

x=2nより
\begin{align}
y^2=8n^3+7 \equiv 7 \bmod 8
\end{align}
により、 7 \bmod 8は平方剰余ではないためyが整数となる解は存在しない。

2. xが奇数の時の証明

まず、両辺に1を足して、右辺を展開していきます。
\begin{align}
y^2+1 &= x^3+8 \notag \\
&= (x+2)(x^2-2x+4)
\end{align}

(3) についてある素数p \equiv 3 \bmod 4で割り切れることを示します。
xが奇数の場合、 x^2は次のようになります。
\begin{align}
x^2 &= (2n+1)^2 = 4n^2 + 4n + 1 \notag \\
&= 4n(n + 1) + 1
\end{align}
この時、奇数の要素となるnについてそれぞれ偶数の場合と奇数の場合で考えると、
偶数の場合: n = 2k
\begin{align}
even: n = 2k とすると 8k(2k+1) + 1 \\
odd: n = 2k+1 とすると 4(2k+1)(2k+2) +1 = 8(2k+1)(k+1) + 1
\end{align}
となることから、
\begin{align}
x^2 \equiv 8n' + 1 \equiv 1 \bmod 8
\end{align}

次に 2xは、
\begin{align}
2x = 2(2n+1) = 4n + 2 \equiv 2 \bmod 4
\end{align}

(6)と(7)より x^2-2x+4は、
\begin{align}
x^2-2x+4 &= 8n+1 - (4n+2) + 4 \notag \\
&= 4n + 3 \equiv 3 \bmod 4
\end{align}
となります。

式(1)と(8)より y^2+1は 3 \bmod 4で割り切れることがわかったので、 p \equiv 3 \bmod 4とすると、以下の式が成り立つ
\begin{align}
y^2+1 &= mp より \notag \\
y^2 &= mp -1 \notag \\
y^2 &= -1 \bmod p
\end{align}
(9)より、ある素数 p \equiv 3 \bmod 4について -1 \bmod pは平方剰余ではないため、yが整数となる解はありません。

Q.E.D

まとめ

平方の定義とか、平方剰余とかについて学ぶいい機会になりました。あと、楕円曲線暗号として普段よく使っているsecp256k-1の式には整数解がないってことを知らなかったので意外な発見でした。ちなみに、bitcoinなどでは実際には y^2 \bmod z \:(z = 2^256 - 2^32 - 977)であり、剰余を用いているため公開鍵はx, y共に整数となっているようです。でも小数の剰余ってどうなるんだろう・・・・？よくわからなくなってきましたw

参考