mattyuuの数学ネタ集

世界は数式で溢れている

有限体Fp上の楕円曲線'のパズル

はじめに

先日職場の勉強会でRSA暗号、楕円曲線暗号について発表をしました。面白いことに話の全体を通してフェルマー(17世紀のフランスのアマチュア数学者)が登場しました。

フェルマーはパスカルと共に確率論を創始するなど、上記の暗号関連の話以外にも重要な仕事を行なっております。フェルマーは17世紀の人ですが、現代社会の根っこの部分に彼が与えた、与えている影響は大きそうです。ただ、今回はこれ以上フェルマーの話はしません。勉強会の資料作成を通して、有限体上の楕円曲線を可視化したのですが(←グラフ書いただけですが)、可視化した楕円曲線を眺めたり、いじったりしているうちに、「パズルとして売り出せるんじゃない?」というような面白い性質を見つけたのでその紹介をしたいと思います。

まず、楕円曲線とは下記で定義されます。

楕円曲線の定義

a、bを定数とし、方程式
\displaystyle y^2=x^3+ax+b
を満たす(x,y)全体の集合(←グラフと呼ぶ)を楕円曲線という。

注1:この記事では上記の一般形を得るために、標数が2、3以外の体K上で考えています。a、bもKの元です。
注2:(右辺のxの3次式)=0は重解を持たないものとします。

中学校や高校で習う関数のグラフは、実数体(\mathbb R)という足し算、引き算、掛け算、割り算ができる世界*1の上で考えています。実数上で楕円曲線のグラフを描くと、例えば下記の図のようになります。

a=1、b=1の場合

f:id:mattyuu:20170129155536p:plain

a=-1、b=0の場合

f:id:mattyuu:20170129155547p:plain

2つ目のy^2=x^3-x (a=-1、b=0)の例でグラフの描き方を簡単に説明します。

x=1のときは、y^2=0となりますからy=0です。(x,y)=(1,0)に赤い点を描きます。同様にx=0、-1のときもy=0となるので、(x,y)=(0,0)、(-1,0)にも赤い点を描きます。

x=2のときは、y^2=6となるので、y=\pm\sqrt{6}です。(x,y)=(2,\sqrt{6})、(2,-\sqrt{6})に赤い点を描きます。先程と違い、1つのxに対して2つのyが対応しました。

x=1/2のときは、y^2=-3/8となるので、これを満たす実数yは存在しません。そのため実数上のグラフではx=1/2のときは描く点はありません。

xを-\inftyから\inftyまで動かしながら、各xに対して方程式を満たすyを同様に求めて(x,y)に点を描いていくと、先程の2つ目のグラフになるのです。

有限体{\mathbb F}_p上の楕円曲線

楕円曲線暗号では、楕円曲線は実数体(\mathbb R)上ではなく、有限体{\mathbb F}_p上で考えます。有限体{\mathbb F}_pが何かわからない方は以前書いた下記の記事を読んでみてください。

mattyuu.hatenadiary.com

{\mathbb F}_pは簡単に言えば集合\{0,1,2,\cdots,p-1\}に適切に足し算、引き算、掛け算、割り算を定義した世界になります。今回の記事では足し算と、掛け算しか使わないため、例として{\mathbb F}_5の足し算表、掛け算表を載せておきます。

足し算表

+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3

掛け算表

× 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

有限体{\mathbb F}_pの復習が終わりましたので、実際に{\mathbb F}_p上の楕円曲線を描いてみましょう。ここでは例としてp=5、a=1、b=1とします。

f:id:mattyuu:20170129155625j:plain

楕円曲線というのに、グラフは繋がってないし、曲がった感じもしませんが、楕円曲線の定義に反してませんし、描き方も実数体上の時と全く一緒です。実数体では-\inftyから\inftyまでの無限個のxに対して、yを求めないとグラフは描けませんでしたが、有限体{\mathbb F}_p上ではp個のxに対してyを求めればよいことが本質的に異なります。

では実際に上のグラフがy^2=x^3+x+1のグラフになっていることを確認してみましょう。

x=0のとき、y^2=1となるので、2乗して1になる数求めればよいことになります。{\mathbb F}_5上では0^2=0、1^2=1、2^2=4、3^2=4、4^2=1より、x=0のときはy=1、4となります。よって(x,y)=(0,1)と(0,4)のマスにピンク色を塗っております。

同様に例えばx=4のとき、y^2=4となります。{\mathbb F}_5上では2^2=4、3^2=4より、(x,y)=(4,2)と(4,3)のマスにピンク色を塗ります。

様子が違うのはx=1のときです。このときy^2=3となりますが、{\mathbb F}_5上では2乗して3になる数は存在しません。そのためx=1の縦列のセルにはピンク色に塗るセルはありません。これは先述した実数体上の楕円曲線の例で、y^2=-3/8の解が存在せず描く点がなかったことと同じです。

今回有限体上の楕円曲線はjavascriptでプログラムを作って描画しています。プログラムの良いところは一回プログラムを作ってしまえばパラメータ(ここではp、a、b)を変えたグラフも容易に描画できることです。手計算、手描きでグラフを作成すると、パラメータを変えるごとに改めて計算を行う必要があります。またpを大きくすると計算自体が大変になります。

さあプログラムの利点を活かして{\mathbb F}_5上の楕円曲線'を全て描画してみましょう。a、bはそれぞれ\{0,1,2,3,4\}の5通りから選ぶことができるので、全部で25通りの楕円曲線'が得られます。

{\mathbb F}_5上の楕円曲線'たち
f:id:mattyuu:20170129155643p:plain

p=23にしても描けます!
{\mathbb F}_{23}上の楕円曲線'たち(出力結果を一部抜粋、実際には23^2=529通りの楕円曲線'が現れます。)
f:id:mattyuu:20170129155655p:plain

はぁはぁ、、楽しい。。

ここで一点白状します。上記には楕円曲線以外のグラフも含まれています。楕円曲線の定義の注2で記載しましたが、y^2=x^3+ax+bの右辺のxの3次式について、(右辺のxの3次式)=0という方程式を作ると、この方程式は重解を持たないという前提があります。例えば{\mathbb F}_5上ではx^3+2x+2=(x-1)^2(x-3)となり、重解を持ってしまうので、{\mathbb F}_5上でy^2=x^3+2x+2は楕円曲線ではありません。

しかし、今回考えたパズルは全てのa、bを対象にしないと成立しません。誠に情けないですが楕円曲線の集合に、楕円曲線とは言ってはいけない{\mathbb F}_5上のy^2=x^3+2x+2といった曲線も追加して楕円曲線'という名前で広い範囲の集合を考えます。

気づいた性質

さて、楕円曲線'のグラフを並べてみると気づくことがあります。それはp、aを固定して、bを0からp-1まで動かしたp個のグラフを重ね合わせると全マスがちょうど1回ずつピンク色に塗られるのです！

言葉だけではわからないと思いますので、つまりこういうことです。
f:id:mattyuu:20170129155713j:plain

つまり、こういうことです。
f:id:mattyuu:20170129155805g:plain

つまり、こういうことです。
f:id:mattyuu:20170129155831g:plain

最後の例ではピンク色の部分はセロハンのような素材と思ってください。セロハンを重ねるごとにピンク色が濃くなります。aが同じ値の時は各セルが足並みをそろえて濃くなっていく様子が確認できます。

p=23でも、綺麗に成り立ちます。(ファイルサイズが大きくなってしまうので、アニメは途中で止めています。)
f:id:mattyuu:20170129155851g:plain

はぁはぁ、、面白い。。

p=97とか、p=691とかもっと大きい素数では楕円曲線'のグラフもより複雑になります。複雑なグラフがp個あり、それを重ね合わせると綺麗なピンク一色！何かに役立つわけではないですが、数学の力を感じさせられます！

この性質が成り立つ証明は超簡単です。残念ながらこの性質は楕円曲線ではない方程式でも成り立ちますし、もっと言えば体{\mathbb F}_p上じゃなく剰余類環{\mathbb Z}_n上でも成り立ちます。

証明

{\mathbb F}_p上の楕円曲線':y^2=x^3+ax+bに対してa=a_0\in {\mathbb F}_pを1つ固定する。この時、下記2点を示せばよい。

  1. \forall (x_0,y_0) \in {\mathbb F}_p \times {\mathbb F}_pに対して、\exists b_0 \in {\mathbb F}_pで{y_0}^2={x_0}^3+a_0x_0+b_0となる。
  2. b_0\ne b_1 \in {\mathbb F}_pのとき、y^2=x^3+a_0x+b_0、y^2=x^3+a_0x+b_1は共通の解を持たない。
  • 1の証明:b_0={y_0}^2-{x_0}^3-a_0x_0とすればよい。
  • 2の証明:(x_0,y_0)が共通の解とすると、{y_0}^2={x_0}^3+a_0x_0+b_0、{y_0}^2={x_0}^3+a_0x_0+b_1がそれぞれ成り立つ。辺々を引くと、b_0=b_1となり、これは前提に矛盾。

証明はいかにも当たり前ですが、可視化してみないと気づかなかった性質なので、満足感はあります。

応用例

楕円曲線'に関して面白い性質を見つけたので、何か応用したくあります。

まずは、大人向けのパズルとして活躍の余地はないでしょうか。p=5のときは、25種類の楕円曲線'が描かれたカードを用意します。色が塗られていない部分は透過するようにしたいためアクリル板で作成しましょう。25枚のカードから適切に5枚ずつ選んで、それぞれの組で各カードを適切に回転、反転させて重ね合わせることで、ピンク一色のカードの組が5セットできたら成功です。*2

f:id:mattyuu:20170129155916j:plain

p=5が余裕でできるようになったら、p=7、p=11と難易度を上げていけば素数の数だけ楽しめます！

次に思いつくのは子供向けの絵合せパズルです。2〜3歳の時はaを固定して、5枚のカードでくまさんの絵合せをしましょう。

f:id:mattyuu:20170129155959g:plain

幼稚園に行きだしたら、ゴレンジャーを題材にしましょう。この頃になると25枚あっても大丈夫なはずです。

f:id:mattyuu:20170129160032g:plain

このように子供の時から素数や楕円曲線'に慣れ親しみ純粋に育った男の子は、プロポーズにもメッセージカードと称して楕円曲線'カードを使用してしまう恐れがあります。

f:id:mattyuu:20170129160100g:plain

おまけ

今回は有限体上の楕円曲線を可視化しました(←グラフ書いただけ)。可視化すると楕円曲線の方程式を満たす解の個数も一目瞭然ですが、この解の個数がフェルマーの最終定理の証明に深く関係しています。また、この解の個数はハッセ・ヴェイユ境界と呼ばれる、より高度な数学にも関連しています。私はステートメントはなんとなくわかるレベルです。

今回楕円曲線とは何かということに関しては何も触れていません。楕円曲線をgoogle検索すると、やはりtsujimotterさんの記事がwikipediaの次に出てきましたので、ここにも貼り付けておきます。楕円曲線の面白いネタがたくさん書かれています。興味がある方は一緒に楕円曲線の勉強をしましょう。
tsujimotter-sub.hatenablog.com

ついでながら、今回ゴレンジャーのアニメはjavascript、canvasで作成したのですが、画像を回転させるのにこれまたtsujimotterさんの下記の記事が大変役に立ちました。原点を中心としてcanvas全体を回転させるのは簡単にできるのですが、画像を中心として、その画像だけを回転させる方法はネットで調べてもよくわからず、ネットサーフィンを続けているうちに下記の記事に行き着きました。参考にこちらも貼り付けておきます。

tsujimotter.hatenablog.com

f:id:mattyuu:20170129160143j:plain

*1:数学的には四則ができる世界を体(たい)と呼ぶ

*2:このパズルを売り出すためには解の一意性を証明しておく必要があります。