Wait a moment...

楕円曲線(だえんきょくせん)の話1 ~~有理点を探せ!~~

nem31.59xem (10)
612
15
2020-03-25 18:02:59
楕円曲線(だえんきょくせん)の話1 ~~有理点を探せ!~~



Nem や Bitcoin では、楕円曲線暗号(だえんきょくせん あんごう)なるものが取り入れられており、
Nem Symbol technical reference にも、楕円曲線 (英語で elliptic curve) という言葉が登場します。

今回は、この楕円曲線(だえんきょくせん)と呼ばれるもののお話をしたいと思います。
この記事も含めて、三つの記事に内容を分けて、紹介していきます。

本記事と、次の記事で、楕円曲線の基本的なお話をして、最後の記事で、楕円曲線がどのように応用されて
いるのか、実際に technical reference の一部と照らし合わせながら、紹介してみたいと思います。



まずは、ちょっとだけ、中学で習う数学をおさらいしてみましょう。


1.おさらい






例えば、上のような式があって、

「〇 (丸)と □ (四角)に数字をあてはめて、正しい式にしなさい」

と言われたら、いろいろな答えをつくることができます。□にを入れてみると、




となって、右辺は 1 + 1 で 2 になるため、〇に 2 を入れてあげれば、正しい式になります:



答えは他にもありますよね。

□ に 2 を入れると、右辺は 2 + 1 で 3 になるため、〇に 3 を入れてあげれば正しい式になります。

□ に 3 を入れると、右辺は 3 + 1 で 4 になるので、 〇に 4 を入れてあげれば正しい式になりますね。
こんな感じで、正しい式になる □、〇のペア を大量生産できます:



↑ これらの □、〇のペアを、座標にプロットしてみましょう。

まず、横軸を□、縦軸を〇の数字にとって、□ = , 〇 = 2 というペアを赤丸でプロットしてあげます。
つまり、原点 0 から、□方向へ+1、〇方向へ+2進んだ点にプロットするのです。以下のようになります:




他のペア   (□=2,〇=3),  (□=3,〇=4),  (□=0,〇=1) もプロットしてあげると



となります。

次は、□にマイナスの数字を入れてみましょう。 □に -1 を入れてあげると、右辺は -1 + 1 で 0 になります。



このように、□にマイナスの数字を入れても、たくさん答えが出きあがります:



てことで、これらもプロットしてあげると、



となります。プロットした点が、直線上に並んでいるのがわかりますね。

□に分数を入れてあげたっていい。□に 1/2 を入れると、右辺は 1/2 + 1 で、 3/2 となります。



□=1/2,  〇 = 3/2 もプロットしてあげると、だいたいここらへん:





□に √2 (ルート2)を入れてあげると、



となる。√2 = 1.41421356...,  √2 + 1 = 2.41421356..., なので、プロットすると、



だいたいこのへんかしら。

こんな感じでプロットを続けると、












というふうに、直線ができあがります。



のような`虫食い計算式' の答えをプロットしていくと、直線などの図形ができあがる
という衝撃の事実を、我々は中学生の頃に突き付けられるわけです。

 

2.有理点



先ほどの例では、穴埋め計算式の □ にいろいろな数字をあてはめてみて、それに合うように、
〇 に数字を入れていきました。この方法で見つかった答えとして、

(□ = 1,  〇 = 2)  や、  (□ = 1/2,  〇 = 3/2)

というものがありました。(□ = 1,  〇 = 2) というペアは、□も〇も、1, 2 という 整数 です。
(□ = 1/2,  〇 = 3/2)というペアは、□も〇も、1/2, 3/2 という 分数 ですね。

今回の記事では、『□、〇の穴埋め計算式』があったとき、(□ = 1,  〇 = 2) や、
(□ = 1/2,  〇 = 3/2)のような

『□、〇 の両方が、`整数'、あるいは`整数と整数の分数' になるような答えを見つけよう!』

という問題を考えてみたいと思います。




少し言葉を整理しますね。

0 、1、2、3、4、5、・・・ というような、0に1を加えていくことで得られる数字、
あるいは、-1、-2、-3、-4、・・・と、0から1を引いていくことで得られる数字のことを整数と言います。

『整数』や、『「1/2」「5/3」 のように「整数と整数の分数」の形で表される数字』のことを、
まとめて有理数(ゆうりすう)と言います。

なので、「有理数」と言ったら、整数や、分数のことを思い浮かべてもらえたら良いです。


※例えば円周率 π だって、分母に1を書けば「π/1」と分数になってしまうので、
「分数」というのは少し曖昧な言葉。。なので、ここでは厳密に「有理数」という言葉を使うことにします。



先ほどの、(□ = 1,  〇 = 2)、(□ = 1/2,  〇 = 3/2) という点は、□も〇も両方とも有理数ですね。
こんなふうに、□も〇も、どちらも有理数である点のことを 有理点(ゆうりてん) と呼びます。


つまり今回は、□、〇の穴埋め計算問題があったとき、
『□、〇 の両方が、有理数になるような答え(=有理点)を見つけよう!』という問題を考えたいのです。




ちなみに、√2 とか、円周率 π などは、整数と整数の分数で表せないことが知られていて、
無理数(むりすう)と呼ばれます。


「1.おさらい」の「〇=□+1」という式の答えとしてプロットした(√2, √2 + 1) という点は、
√2 が有理数ではないため、有理点ではありません。

「〇=□+1」 というような場合ですと、□に有理数を入れれば、〇も自動的に有理数となるため、
有理点を見つけるのはとても簡単です。


なのですが!


〇と□の式が、ちょっと複雑になると、有理点を求めるのが、とたんにメチャクチャ難しくなるのです!



3.有理点を探せ!




例えば、次の場合を考えます。



二つの〇には同じ数字を入れないといけません。三つの□にも、同じ数字を入れますよ。

なんだか答えを一つ見つけるのも難しいように思えますが、「1.おさらい」で扱った直線の例と同様、

『□に何か数字を入れて、それに合わせて〇に数字をあてはめる』という作戦で、正しい式を完成させてみましょう。

□にを入れますと、



となって、右辺は 1+2=3になります。〇×〇=3なので、〇に√3をあてはめれば、正しい式になりますね:



しかし、√3は有理数ではないため、(□=1、〇=√3) は有理点ではありません

次に、□にを入れてみましょう。すると、右辺は2×2×2+2=10となります。
なので、〇に√10 を入れれば正しい式になりますが、√10 が有理数ではないので、
□=2、〇=√10 も有理点ではありません:



直線の例とは対照的で、□に有理数を入れても、〇が有理数になるとは限らないんです。

□に 3,4,5 と数字を入れてみても、



と、全然、有理点が出てきません。

そこで、□に -1 を入れてみましょう。すると、右辺は、(-1)×(-1)×(-1)+2 =1
となります。なので、〇に1を入れてあげれば、



と、正しい式になります。□= -1, 〇= 1 はともに有理数なので、有理点です

やっとこさ、有理点が見つかりました。


他に有理点はないのでしょうか? 次は □に分数を入れてみます。

□に 1/2 を入れると、右辺は、(1/2)×(1/2)×(1/2)+2=17/8 となる。
残念ながら、2乗して 17/8 になるような有理数は存在しないため、ルートを使って
〇=√17/8  と書くしかありません:



続けて、1/3, 1/4, 1/5 と分数を入れていっても



と、ことごとく、有理点じゃない点が出てきます。

もう有理点なんかないんじゃないの?と思いきや、□に 17/4 という数字を入れますと、

右辺=(17/4)×(17/4)×(17/4) + 2 = 5041/64

となります。この計算結果 5041/64 は、71/8 × 71/8 = 5041/64  と、(71/8)という有理数を2乗したもの
になっているのです。 なので、□=17/4, 〇=71/8 は、先の方程式を満たす有理点です:





先ほど、□に 1,2,3,4,5 と入れてみたり、1/2,  1/3,  1/4 という数字をあてはめてみたり

しましたが、〇は有理数になりませんでした。ほとんどの場合、□に有理数を入れても、
〇は有理数になりません



なのですが!


ごくまれに!ごくまれにですよ。GOKU MARENI !

ごくまれに、上の例のように、□に有理数を入れたら、「右辺の計算結果=有理数の2乗」となって、
うまい具合に□も〇も有理数の形で書けることがあるのです。

何も知らない人が、□=17/4 という答えに辿りつくのに、果たしてどれだけの時間がかかるでしょうか。


他にも、『ごくまれに!』が起こるのが、□=127/441 という有理数をあてはめた場合。右辺は、



となります。きなくさい分数が出てきました。この計算結果 173580625/85766121 は、なんと

173580625/85766121 = 13175/9261 × 13175/9261

と、有理数13175/9261を2乗した形になっているのです。なので、〇に 13175/9261 を入れると、
正しい式になります。




□=127/441, 〇=13175/9261 なんて答え、自力で辿りつくのなんか不可能ですよね。


今の例(〇×〇=□×□×□+2)では、式の中で〇が2乗、□が3乗された形になっていますね。
このように、「穴埋め計算式」の中の 〇、□が、両方とも2乗、3乗、あるいは4乗以上 されていると、
有理点を求めるのが、とてもとても難しい問題になってしまうのです。



今見つけた、〇×〇=□×□×□+2 の答えとなる点をいくつかプロットしてみると以下のようになります:


↑有理点を赤点、有理点じゃない点を青点で記しました。


1. の 「〇=□+1」という例では、答えをプロットしていくと直線が作り出されましたが、
今回の場合は、プロットを続けていくと、次のような曲線が作り出されます(有理点の色分けはしていません):




実は上の曲線は、今回の主題にもなっている「楕円曲線(だえんきょくせん)」と呼ばれる曲線の一つです。

この紺色で描かれた曲線のうち、いったい有理点はどこにあるのか。
それを求めるのは難しい問題だと書きましたが、今回の例(〇×〇=□×□×□+2)を含む
楕円曲線については、有理点を見つける `うまい方法'が知られているんです。



4.計算と図形




その`うまい方法' というのは、一つ有理点が見つかると、そこから次から次へと有理点を見つけていくことができる
というものです。どういうことか。詳しく見ていきましょう。



4-1. 有理点が一つ見つかると、もう一つ有理点が見つかる



がんばって有理点 を一つ見つけると、そこからもう一つ、有理点を見つけることができます。

曲線上のどこか一点を、と名付けましょう。次の2ステップで、新しく決定される一点に注目します。

Step 1.  点の接線を引く



の接線を引くと、特殊な例外を除き、その接線は、曲線と、ある一点で必ず交わります。
(`特殊な例外'については次回の記事で)


Step 2. その交わった点と、横軸に関して上下対称のところにある点に注目



楕円曲線は、上下対称な形をしています。
そのため、Step 1. の交点の上下反対側にある点に注目します。すると、次の定理が成り立ちます。

定理点Pが有理点なら、この注目した点も、有理点である。




3.で扱った(〇×〇=□×□×□+2)の例を見てみましょう。P=(□=-1, 〇= 1) が、最初に見つけた
一つの有理点でした。

の接線を引いてみますと、



となります。すると、この直線は、曲線とある一点で交わります。その交わった点と、横軸に関して
上下反対側にある点は、




と、(□=17/4, 〇= - 71/8)という座標を持ちます。
定理が言っている通り、確かに、点Pが有理点だったら、Step1, 2 で注目される点も有理点ですね。

3.で(□=17/4, 〇= - 71/8)が方程式 〇×〇=□×□×□+2を満たす有理点であることは確認しました。

(細かく言えば、3.では、□=17/4,  〇= 71/8 としていましたが、〇=71/8 でも -71/8 でも、
2乗してしまえば、マイナスの有無は見えなくなりますね。)

このように、一個有理点が見つかると、もう一つ有理点を見つけることができます。



4-2.有理点が二つ見つかると、もう一つ有理点が見つかる



有理点が二つ見つかると、もう一つ有理点が見つかります。やり方は4-1で紹介した方法と、とても似ています。

曲線上の二点を P, Q と名付けます。

Step1. 二つの点を直線で結ぶ

二つの点 P, Q を結ぶ直線を引きます。そうすると、特殊な例外を除いて、その直線はある一点と必ず交わります
(この例外についても次の記事に書きます):






Step 2. その交わった点と、横軸に関して上下対称のところにある点に注目



3-1でやったのと同じように、横軸に関して上下対称にある点に注目する。すると、次が成り立ちます。

定理P, Q が有理点だったら、この注目した点も、有理点である。




3. で扱った例をもう一度。(□=-1, 〇=1)(□=17/4,  〇=- 71/8) は、〇×〇=□×□×□+2
を満たす有理点でしたね。この二点から、もう一点、有理点を見つけてみましょう。

(□=-1, 〇=1) (□=17/4,  〇=- 71/8) を結ぶ線を引いて、



曲線とぶつかった点の上下対称の場所にある点に注目すると、



それは、(□=127/441 〇=13175/9261)という点です。
これが 〇×〇=□×□×□+2を満たす有理点であることは、3.で確かめました。


有理点が二つ見つかると、そこから、もう一つ有理点が見つかるのです!



4-3. 有理点を探す旅



4-2の方法が強力なのは、それを繰り返し使うことができるというところ。


・有理点が一つ見つかったとしましょう。それを「有理点1」と名付ける。
 4-1の方法で、もう一つ有理点を見つけることができます。それを「有理点2」と名付けましょう。

・「有理点1」と「有理点2」から、4-2の方法で、新しく「有理点3」を見つけることができます。

・「有理点1」と「有理点3」から、4-2の方法で、新しく「有理点4」を見つけることができます。
・「有理点1」と「有理点4」から、4-2の方法で、新しく「有理点5」を見つけることができます。

4-2の方法を繰り返すことで、有理点が次から次へと見つかっていくのです。

先ほどの 〇×○=□×□×□+2の例では、有理点(□=-1, 〇=1)から出発し、4-1の方法で、
(□=17/4, 〇=-71/8)という有理点を見つけました。


そのあと、二つの有理点(□=-1, 〇=1), (□=17/4, 〇=-71/8)から、4-2の方法で、
(□=127/441, 〇=13175/9261) という有理点を見つけました。


これをさらに続けると、二つの有理点 (□=-1, 〇=1), (□=127/441, 〇=13175/9261) から、
4-2の方法で、(□=66113/80656, 〇=- 36583777/22906304 ) という有理点が新たに見つかります。


さらに、二つの有理点(□=-1, 〇=1), (□=66113/80656, 〇=- 36583777/22906304 )から、
4-2の方法で、

(□=108305279/48846121, 〇=1226178094681/341385539669 ) という有理点が見つかります。




  ↑ IT'S MAGIC !! ↑


このように、一つ有理点が見つかると、4-1の方法で有理点が一つ見つかり、さらに4-2の方法を繰り返し使う
ことで、次から次へと有理点が見つかっていくのです。普通の計算では、あんなに見つけるのがムズかしかったのに。

〇×〇=□×□×□+2という例の場合、この方法で、無限に有理点が見つかります。



線を引いて、曲線と交わった点の上下対称の点に注目する。図形的には、やってることはとてもシンプルですね。

ただ、この方法で注目される点の座標を、正確に計算するのは、どのようにしたら良いのか。

これについては、微分や関数論が得意な方は、それらを使って計算してもらってもいいですし、
もっと言うと、座標を求めるための公式がありますので、それを使えば簡単に求まります(詳しくは`あぺんでぃくす'で)。



5.楕円曲線



以上の方法は、(〇×〇=□×□×□+2)という曲線を含む`楕円曲線'(だえんきょくせん)
と呼ばれる曲線に対して、有効な方法です。さて、楕円曲線とは何でしょうか。

(〇×〇=□×□×□+2)という式は、〇、□を y, x に置き換えると、



と書けます。一般に、


という形の式で、右辺の判別式が0にならないものは、楕円曲線と呼ばれます。
(本記事では、係数 a, b, c は有理数としておきます。)

「楕円曲線」の定義は、本当はもっと幅広いのですが、本記事と次の記事では、「楕円曲線」と言ったら、
上記のようなものを想定しているとします。


判別式というのは、右辺の係数 a,b,c を使って



と計算される数字です。複雑な式ですが、これが0より大きいか、小さいかで、
グラフの形が次のように変わります:



左から二番目、右から二番目の、判別式が0のグラフを見ると、尖った点があったり、クロスしてる点が
あったりしますね。

楕円曲線では、こういうことが起こらず、一番左か、一番右のグラフのような形になります。

「楕円」というと、円を押しつぶしたような図形を思い浮かべますが、楕円曲線は、楕円ではありません
楕円の研究の中で登場した、という歴史的な経緯から、このような名前がついています。





楕円曲線は個性豊かで、有理点をほんの数個しか持たないものもあれば、今回の「〇×〇=□×□×□+2」
のように、有理点を無限に持つものもあります。

(4-2の方法を繰り返し使っても、最初の点に戻ってきてしまうこともある。)

今回ご紹介したのは、「一つの有理点から、他の有理点を発見する方法」でしたが、
「有理点を全て発見する」というのは、これまた難しい問題です。

楕円曲線の有理点に関する未解決問題で、BSD予想と呼ばれる数学の難問があります。
(ーチさん、ウィンナートン=イアーさんという二人の数学者が立てた予想です。二人の頭文字を取って、BSD).

これは、ざっくり言えば、「楕円曲線がどれくらい有理点を持つか」を調べる方法を提案するものです。
この問題を解決すると、アメリカのクレイ数学研究所から、100万ドルの懸賞金をもらえることが
約束されています。レッツチャレンジ!





ともあれ、「方程式を満たす有理点を求めなさい」という計算問題が、図形的な考え方で解決されていくのでした。

数学というのは不思議なもので、そういう`良い考え方' が見つかると、全く予期しない応用に繋がったりするもの。

この`良い考え方' は、冒頭で述べた「楕円曲線暗号」という、Nem や bitcoin などで使われる暗号の誕生に繋がることになります。


つづく


参考文献
・J. H.シルヴァーマン,J.テイト, 足立恒雄 他 訳「楕円曲線論入門」



あぺんでぃくす1



楕円曲線



の点 P=(X,Y) があったとき、4-1.の手順で注目される点の座標は、以下の公式で与えられます:



最初に、上の公式に係数 a,b,c と Pの座標 X,Y をあてはめていって、X’の値を計算します。
さらに X' を下の公式にあてはめることで、4-1.の手順で注目される点の座標が求まります。

3.で扱った例 (〇×〇=□×□×□+2)、つまり y^2 = x^3 + 2 という楕円曲線を例に考えてみましょう。
a=0, b=0, c=2 です。P=(-1,1) という曲線上の点に対して、上の公式を適用すると、



となって、これを下の公式にあてはめると、4-1の手順で注目される点は、


 
という点になります。



あぺんでぃくす2



楕円曲線



の点P=(X_1, Y_1),  Q=(X_2, Y_2)に対し、4-2.の手順で注目される点の座標は、
以下の公式で与えられます:



 上の公式に現れる λ, ν は、P, Q を通る直線の傾き、切片です。最初にこれらを求めて、
下の公式にあてはめることで、4-2.の手順で注目される点の座標が求まります。
(νは、 Y_1 - λX_1 または Y_2 - λX_2 の計算しやすい方で計算すればOK)

3. で扱った例 y^2 = x^3 + 2 を考え、曲線上の点を P=(-1,1),  Q=(17/4, -71/8)
として、4-2.の手順で注目される点の座標を求めてみましょう。まず、λとνを求めます:



てことで、これを下の式に代入すると、4-2の手順で注目される点は、以下のようになります:





これで有理点求め放題!



Comment
やってみよう
やってみよう
2020-04-07 15:02:48ID:182423

>>サバトラ::さん

今回は特に内容が複雑でした。
どうしても「有理数」のことを記事にしたくて、
ルートや、分子分母が大きい分数などが登場してしまいました。
それでも読んでくださり、ありがとうございます!

サバトラ
サバトラ
2020-04-07 13:33:18ID:182397

遅くなりました。
何度もトライしましたが、ギブアップ!
かなり集中しないと…いや私の場合は、
集中しても難しいです。/(^o^)\
私のわかったのおさらいの所だけ〜😅

やってみよう
やってみよう
2020-03-27 00:03:50ID:181136

>>オーウェン::さん

ありがとうございます!
まさに「見つけた!」て感覚だったでしょうね。
そういう嬉しい経験が、数学を研究し続ける原動力になるんだろうなって思います。

オーウェン
オーウェン
2020-03-26 22:01:38ID:181114

こういうのを見つけてしまった時にエウレーカって叫ぶんだろうなと思った。
面白い😇

やってみよう
やってみよう
2020-03-26 18:00:02ID:181092

>>煤::さん

ありがとうございます。ほんと、考えた人たちはすごすぎですよね。
楕円曲線の性質をうまく利用して、クラッカーのあらゆる攻撃に耐えられるように
考えつくされて、楕円曲線暗号ができあがっているようです。

やってみよう
やってみよう
2020-03-26 17:59:36ID:181091

>>amarin123::さん

ありがとうございます!記事を書いた甲斐がありました。
楕円曲線上の「加算(足し算)」の話などは、他の解説でも取り上げられていると
思うのですが、実はこういう背景がありました。

>>ぺぺ α::さん

「初歩」と書いておきながら内容は複雑!は、数学あるあるですw
次の記事では「有理点」「√」「分子分母が巨大な分数」の話は出てきません。
4-1、4-2の Step1,Step2 の操作が重要になります!

煤
2020-03-26 16:39:47ID:181089

難しいけど面白い!!
こんなことをあーだこーだして、暗号通貨ができているんですね。
考えだした人すごすぎる…

amarin123
amarin123
2020-03-26 10:24:56ID:181066

はじめてしっくりくる説明に出会えました!!
ちょっとぼくも理解を深めようと思います!!

ぺぺ α
ぺぺ α
2020-03-26 02:07:11ID:181039

こっ、これが初歩ですか?(・_・;
最初は超簡単で楽勝かと思ったら・・・😇

どこまで近づけるか分からないけど、繰り返しますね!

やってみよう
やってみよう
2020-03-25 22:15:09ID:181011

>>ゼム🐳ゼム.::さん

無限にあるから好きなだけ持ってってー!
計算を頑張れば無料でゲットできちゃいますー。

>>7zoesan::さん

Nem をクラッキングしようとする人は、
楕円曲線を読み解かないといけないのです!
きっとこの複雑さが、クラッカーにとっての障害になるハズ。。

この記事を書いた人
数学関連の記事が多めです。