SSブログ

No.316 - 高校数学で理解する楕円曲線暗号の数理(2) [科学]

前回より続く)

前回の No.316「高校数学で理解する楕円曲線暗号の数理(1)」では「有限体上の楕円曲線で定義された加法群」までの説明をしました。楕円曲線暗号はこの加法群で構成します。今回はその説明ですが、まず、加法群の点をどうやって見い出すか、またこの加法群の点の総数はどうなっているのかです。


16. 楕円曲線上の点


F p の元 xy のぺア xy の集合を F p  2 と記述します。集合 F p  2 の元で楕円曲線上の "点" はどれだけあるでしょうか。まず、楕円曲線の式を満たす F p  2 の元がどのように計算できるかを調べます。

 平方数と平方根 

楕円曲線の式を、

{ y2 = z z = x3 + ax + b

と書くとき、z z0 )が F p での平方数なら、y の解が2つ求まります。ここで、次の命題が成立します。

16.1  平方数である条件

z0 ではない F p の元とする。

z p-1 2 = 1

であるとき(かつ、そのときに限り)z は平方数である(= オイラーの規準)。


F p で考えているので「平方数」と書きましたが、整数の世界では「平方剰余」です。つまり、 x2 = a modn となるような x が存在する a が平方剰余です。16.1 の証明ですが、 F p から 0 を除いた乗法群 F p で考えます。12.1(No.313)により、z F p の生成元(の一つ)を g として、

z = gk

と表現できます。つまり、命題の条件は、

g k p-1 2 = 1

です。このとき k は偶数のはずです。なぜなら、もし k が奇数だとすると、 k p-1 2 p-1 で割り切れないので、

k p-1 2 = sp-1+t 1 t < p-1

と表現できます。すると、

g k p-1 2 = g sp-1+t = gp-1 s · gt = gt

となり、 gt = 1 1 t < p-1 になりますが、これは g が生成元であることと矛盾します。従って k は偶数です。そうすると k=2m とおいて、

z = g m 2

となり、z は平方数になります。



z は平方数だとわかったとき、実際に F p y(= z の平方根)を求める手段が必要になります。整数であれば平方数の平方根を求めるのは容易ですが、 F p ではそうはいきません。特に、楕円曲線暗号で使われる p は10進数で数10桁以上の巨大素数なので、総当たりで求めたり、解の存在範囲を限定していって求めるわけにはいかないのです。ただ、もし p 3 mod4 なら求めるのは容易で、

y = z p+1 4

が解の一つとなります(もう一つの解は -y で、つまり p-y )。確認してみると、

y2 = z p+1 4 2 = z p+1 2 = z p-1 2 · z = z

となって、確かに y が解であることがわかります。しかし、 p 1 mod4 なら、このような簡便な式では求まりません。この場合は「トネリ - シャンクスのアルゴリズム」で解を求めます(Tonelli は19世紀イタリア、Shanks は20世紀米国の数学者)。なお、このアルゴリズムは説明が長くなるので割愛します。



いま、 F p において z0 から p-1 まで振ったときの y2 = z の解の総数を求めてみます。z を、 F p の生成元 g を使って、

z = { 0 gk k = 1 2  ⋯  p-1

と表すと、

・  z = 0 のとき、解は1個
・ k が偶数のとき、解は2個
・ k が奇数のとき、解は無し

となり、 F p  2 における解、 zy の総数は p となります。では、 F p  2 における楕円曲線上の点、 xy の総数はどうなるでしょうか。x F p の全ての元に渡るとき、z F p で均等にバラつくとは限りません。しかし xy の総数は「だいたい p に近い値」だと考えられます。

つまり、群 Eabp の元で、零元 O 以外の F p  2 に属するものは、だいたい p 個あると考えられる。群 Eabp の元の数を #E と書くと、 #E は 零元 O を含んで p+1 に近い値だと考えられます。

Eabp の元の数を評価する式があります。「ハッセの定理」です(Helmut Hasse は20世紀ドイツの数学者)。この定理にによると、

p+1-2p #E p+1+2p

であり、想定どおり #E p+1 の周辺であることが分かります。 #E を具体的に求めるアルゴリズムは、1985年にオランダ出身の数学者、レネ・ショーフ( Rene Schoof。英語読みでスクーフとも書かれる)が開発しました。その「ショーフのアルゴリズム」は、数学用語で言うと最初の「決定論的多項式時間アルゴリズム」です。平たく言うと「計算結果が100%正しいと数学的に保証される(=決定論的)計算可能な(=多項式時間)アルゴリズム」です。「ショーフのアルゴリズム」の具体的内容は、ここでは割愛します。


17. 位数


楕円曲線暗号を構成する上で必要になるのが、有限群における「位数」の概念です。以下の位数の話はすべての有限群に共通するので、群の演算を乗法的に書くことにします(掛け算、冪乗、単位元 e、などの記法を使います)。演算を加法と考えても全く同じことになります。

元の数が有限個の群 G を「有限群」といい、その元の個数を「群位数(group order)」と呼びます。群位数を |G| と表します。群の演算則だけから次のことが言えます。

単位元 e でない群 G の元を a とします。a の冪乗 an 1n n を増やしていくと、ある時点で an = e となります。その理由ですが、

a1 a2  ⋯  a |G|

という |G| 個の元を考えてみます。もし |G| 個が全て相異なると、どれかが e のはずです。全てが相異なる元ではないとき、

aj = ai 1 i < j |G|

となったとすると、 ai の逆元を右から掛けて、

aj-i = e

が得られます。 1 j-i < |G| なので、この範囲に e があります。そこで、つぎのように元 a位数を定義できます。

17.1  位数の定義

有限群 G の任意の元 a について、

a d = e

となる最小の da の "位数(order)" と言う。



さらに、元の位数については次の命題が成り立ちます。

17.2  位数と群位数

有限群 G の任意の元 a の位数を d とすると、d は群位数 |G| の約数である。


この命題が成り立つ理由は次の通りです。有限群 G の任意の元を a とし、集合 A を、

A = a1 a2  ⋯  ad = e

とします。集合 A の元は全て相異なります。なぜなら、もし、

aj = ai 1 i < j d

となったとすると、

aj-i = e

であり、d ad = e となる最小の数であるという位数の定義に反するからです。さらに、集合 A の任意の元の逆元は集合 A に含まれます。つまり、 ad = e なので aj 1j<d に対して ad-j 1d-j<d が逆元です(ということは集合 A もまた群であり、これを G の部分群と言います)。

集合 AG の全ての元を尽くしているなら 17.2 は成立します。そこで、集合 A に含まれない G の元があったとし、それを b1 とします。集合 A の全ての元に左から b1 を掛けて、集合 B1 を作ります。つまり、

B1 = b1 a1 b1 a2  ⋯  b1 ad

です。集合 A の元は全て相異なるので、集合 B1 の元も全て相異なります。さらに、集合 B1 の元で集合 A の元と同じものはありません。なぜなら、もし、

b1 ai = aj 1 i < j d

だとすると、 ai の逆元、 ad-i を右から掛けて、

b1ad = ad-i+j b1 = ad-i+j = aj-i

となりますが、 1 j-i < d なので、これは b1 が集合 A の元であることを意味していて仮定に反します。つまり、集合 B1 の元で集合 A の元と同じものはありません。

集合 A B1 G の元の全てを尽くしているなら、 2d = |G| となって 17.2 は証明できたことになります。そうではない場合、集合 A B1 に含まれない G の元の一つを b2 として、集合 B2 を、

B2 = b2a1 b2a2  ⋯  b2ad

と定義します。そうすると先ほど同じように、集合 B2 の元は全て相異なり、かつ、集合 A との重複はありません。さらに、集合 B2 の元は集合 B1 の元とも重複しません。なぜなら、もし、

b2ai = b1aj 1 i < j d

だとすると、 ai の逆元、 ad-i を右から掛けて、

b2 = b1 ad-i+j = b1 aj-i

となりますが、 1 j-i < d なので、 b2 が 集合 B1 の元という意味になり仮定に反します。つまり、集合 B2 の元は集合 B1 の元と重複しません。

以上の操作は G の元が残っている限り B3 B4  ⋯  と続けられます。そしてある時点で 残っている G の元がちょうど切りのよいところで無くなるはずです。 Bn-1 まで作ったときに G の元の全てを尽くしたとしたら、 nd = |G| です。これで 17.2 が証明できました。17.2 から直ちに次の2つが結論づけられます。

17.3  

有限群 G の任意の元 a について、

a |G| = e

である。


これは、群位数 |G| が 元 a の位数の倍数なのでそうなります。p を素数とし、Gp 未満の自然数からなる乗法群 F p だとすると、 |G| = p-1 なので、フェルマの小定理( 3.1 )そのものになります。


17.4  群位数が素数の群

有限群 G の群位数 |G| が素数だとすると、

単位元 e を除く G の全ての元の位数は |G|

である。


素数の約数は 1 と素数自身しかないので、単位元以外の元の位数は群位数に等しくなります。従って、群位数が素数の群では任意の元 a の冪乗が群全体に "バラける" ことになります。


楕円曲線暗号の構成:スカラー倍と離散対数


ここから具体的な楕円曲線暗号のしくみに入ります。楕円曲線上の F p  2 の点と零元 O が作る加法群を Eabp とし、その群位数を #E と書きます。楕円曲線暗号では Eabp における「スカラー倍」の演算を利用します。

楕円曲線上の F p  2 の点の一つを B = Bx By とし、dB の位数、n 1 n d とします。Bn 倍(=スカラー倍)を nB と書き、

nB = B + B +  ⋯  + B n

と定義します。そして、

nB = A

と書くことにすると、A を求める計算は、 Eabp の2倍式と加法式を使って可能です。例として 133 B の場合だと、 133 = 27 + 22 + 1 なので、

133 B = 27 B + 22 B + B

となります。つまり、 Eabp の2倍式を7回使って、

21 B ,   22 B ,    ⋯  ,   26 B ,   27 B

と順次計算し、加法式を2回使うと A が求まります。これは n がたとえ巨大数であっても可能です。 2256 は10進数で約80桁(256ビット)の巨大数ですが、それでも256回程度の2倍算と最大で256回程度の加算をすれば A が求まります。このあたりは 4.2 の「冪剰余の計算アルゴリズム」と同じです。もちろん冪剰余と違って、2倍算も加算も単純な掛け算ではありません。 Eabp の群演算は、定義式どおりの少々ややこしい式です。しかし計算が可能なことは確かです。

スカラー倍の計算は可能ですが、その逆、つまり AB を知って n 求めるのは困難になります。この n を求める問題を、加法群 Eabp における「離散対数問題」と呼びます。離散対数問題を解くのが不可能になるのは、B の位数 d が10進数で数10桁以上といった巨大数の場合です。その場合、Ad 種のバリエーションをとるので、n を求めるのは不可能になります。

位数 d が巨大数である B を求める方法の一つは、p を巨大な素数とし、群位数 #E も素数であるような Eabp を選ぶことです。そうすると 17.4 により、零元 O 以外の Eabp の全ての元の位数 d #E になり、その #E p+1 の近辺にあるので、B をどのように選ぼうとも位数 d は巨大数になります。

#E が素数である Eabp では、任意の元 AB について、 nB = A となる n が唯一存在することになります。このことを、

logB A = n

と書くと、B は実数における通常の対数の "底(base)" に相当します。B Eabp の元 = F p  2 の元なので、B を「ベースポイント(base point)」と呼びます。このペースポイントを含め、楕円曲線暗号では、

・  Eabp
・  #E
・  B = Bx By
・ dB の位数)

が公開されます。そして暗号化通信では、d より小さい数 k をランダムに選び

・ 公開鍵 : kB  
・ 秘密鍵 : k

とします。公開鍵だけを知っても秘密鍵は計算できない。これが楕円曲線暗号の原理です。



スカラー倍のイメージをつかむため、p がごく小さい数の場合で実験してみます。計算してみると、 p=29 ,   a=-1 = 28 ,   b=1 のとき #E = 37 となって、群位数が素数になります。 y2 = x3 - x + 1 の解の一つは 01 なので、これをベースポイント B としてスカラー倍を順次計算してみると次の通りとなります。

 B=(01 )   2B=(2210 )   3B=(2713 )   4B=(924 )   5B=(1418 )   6B=(1125 )   7B=(2320 )   8B=(128 )   9B=(268 )   10B=(223 )   11B=(324 )   12B=(11 )   13B=(2828 )   14B=(518 )   15B=(175 )   16B=(2517 )   17B=(2021 )   18B=(1018 )   19B=(1011 )   20B=(208 )   21B=(2512 )   22B=(1724 )   23B=(511 )   24B=(281 )   25B=(128 )   26B=(35 )   27B=(26 )   28B=(2621 )   29B=(1221 )   30B=(239 )   31B=(114 )   32B=(1411 )   33B=(95 )   34B=(2716 )   35B=(2219 )   36B=(028 )   37B=(O    

群位数が素数なので B の位数は 37 となり、群位数と一致します。この計算を F p  2 の平面に表示すると次の通りです。B 36B は赤丸、 2B 35B は黒丸です。矢印は加算を示し、赤矢印は B+B 35B+B の加算です。

スカラー倍.jpg
図15: E -1 1 29 (零元を除く) #E = 37 ,   B = 01 ,   d=37  

スカラー倍を繰り返すごとに "楕円曲線" 上の合計36点を通り、それが乱雑に変化することが分かります。



振り返ってみると、RSA暗号(No.311)の安全性は巨大数の因数分解の困難性に依存しているのでした。またディフィー・ヘルマンの鍵交換(No.313)は、乗法群 F p における離散対数問題を解くことの困難性に依存しています。これらに使われる演算はいずれも整数の乗除算です。それに対して楕円曲線暗号に使われるのは、整数の乗除算よりは遙かに複雑な、楕円曲線上の加法群における「加算」です。ここに楕円曲線暗号の解読しにくさの要因があります。



実用的な楕円曲線暗号で公開するパラメータをどうやって作るか、その一例をあげます。


① 素数の大きさを決め(たとえば10進数で50~100桁程度)、素数判定法によってその大きさの素数 p を求める。

②  p より小さい数、ab をランダムに決め、加法群 Eabp の群位数 #E を計算する。

③  #E が素数なら次へ。素数でなければ ② に戻る。

④  p より小さい数、 Bx をランダムに選び、 Bx が平方数ならその平方根 By を求めてベースポイント B = Bx By とする。


#E が素数なので、B の位数 d #E に等しくなります。なお、 #E がたまたま p と一致すると離散対数問題が解けることが分かっているので、③ でそのようなケースを排除しておきます。

この決め方では、群位数 #E の計算と素数判定を繰り返すことになり、多大な計算時間がかかることは想像に難くありません。しかしパラメータは1度計算すれば暗号通信の仕様として公開し、皆がそれを使えばいいわけです。最初の1回だけの計算時間より、その後の通信の安全性の方が重要です。

楕円曲線暗号のパラメータの一例を次に掲げます。secp160r1 という名称で公開されているパラメータです。

secp160r1
 
p= 1461501637330902918203684 832716283019653785059327 = 2 160 - 231 - 1 a= 1461501637330902918203684 832716283019653785059324 = p - 3 b= 1632357913061681105466049 19403271579530548345413 #E= 1461501637330902918203687 197606826779884643492439 Bx = 4258262317238883504465415 92701409065913635568770 By = 2035201141629041078739914 57957346892027982641970 d= 1461501637330902918203687 197606826779884643492439 =#E


楕円曲線暗号版ディフィー・ヘルマンの鍵交換(ECDH)


ディフィー・ヘルマンの鍵共有(No.313)を、楕円曲線暗号を使って実現できます(ECDH と略称される)。鍵共有のプロセスは次のように進みます。しかるべき「公開鍵センター」が、皆が使う公開鍵として、

・  Eabp
・  #E
・  B = Bx By
・ dB の位数)

をオープンにして(暗号通信の仕様書として公開して)おきます。以下のスカラー倍演算はすべて F p で行います。AliceBob が秘密鍵を共有したい場合、

暗号文による通信の開始にあたって、Alice 0 < kA < d である乱数 kA を発生させ、 kA B Alice の公開鍵として(盗聴されている通信路を介して) Bob に送付

します。乱数 kA Alice の秘密鍵として秘匿します。次に同様に、

Bob 0 < kB < d である乱数 kB を発生させ、 kB B Bob の公開鍵として(盗聴されている通信路を介して) Alice に送付

します。もちろん kB は秘匿します。そして、

Alice KA = kA kB B を共有の秘密鍵

Bob KB = kB kA B を共有の秘密鍵

とします。この作り方から KA = KB = K となるので、秘密鍵 K を共有できたことになり、以降はこれを使って暗号化通信(公開鍵ではない、高速な暗号化通信)を行います。使った秘密鍵は通信が終わったら捨てます。

原理は、オリジナルのディフィー・ヘルマンの鍵交換(DH)と全く同じです。ただ、オリジナルが F p での離散対数問題を利用していたのに対し、ECDH は Eabp での離散対数問題を利用した暗号であることが違います。


18. 結合則が成り立つことの証明


楕円曲線論入門.jpg
J.H.シルヴァーマン、J.テイト
「楕円曲線論入門」
楕円曲線暗号が暗号として成立するのは、楕円曲線上の加法群 Eabp が "群" として定義できるからです。群であるための条件は「単位元の存在」「逆元の存在」「結合則の成立」の3つです。このうち単位元の存在と逆元の存在は、そもそもそれが成り立つように群の演算を定義したのでした。

しかし結合則は自明ではありません。前回 No.315 の「楕円曲線上の有理点が作る加法群」のところで結合則が成り立つことの証明を後回しにしたので、ここに書くことにします。結合則が成り立つのは、楕円曲線上の有理点の加法を「3次曲線と直線の交点」で決めていることに理由があります。その理由を説明したいと思います。

前回で引用した、シルヴァーマン、テイト著「楕円曲線論入門」には、結合則が成り立つことを示した次の図があります。加法群の零元 O を楕円曲線上にとった場合の図です。

図K:結合則の検証.jpg
図11:結合則
「楕円曲線論入門」より引用

楕円曲線上に点 PQR をとったとき、

P+Q + R = P + Q+R

となるのが結合則ですが、

P+Q +R = P+Q R O P+ Q+R = P Q+R O

です。ここで の記号は、 A B と書くと AB を結ぶ直線が楕円曲線と交わる点(で AB 以外の点)の意味です。O は零元でした。従って、結合則を証明するためには、

P+Q R = P Q+R

が証明できればよいことになります。言葉で書くと、


P+Q R を通る直線が楕円曲線と交わる点を T1 とし、P Q+R を通る直線が楕円曲線と交わる点を T2 とすると、 T1 T2 は同じ点である


となります。上の図はそれを表しています。以下の証明では同じことですが、次を示します。

18.1  結合則

P+Q R を結ぶ直線と、 Q+R P を結ぶ直線の交点を T とすると、楕円曲線は T を通る。


これは楕円曲線上の2点、 P+Q R P Q+R が等しい(= 図11)ことと同じなので、以降は 18.1 が成り立つことを示します。そのためにまず、次の命題 18.2 を証明します。この証明の筋道は「楕円曲線論入門」に書かれているものです。

18.2  3つの3次曲線の交差

2つの3次曲線、 C1 C2 が相異なる9点、 P1 ,   P2  ⋯  ,   P9 を通るとする。

別の3次曲線 D が 9点のうちの8点、 P1 ,   P2  ⋯  ,   P8 を通るとき、D P9 も通る。


これは「ケーレー - バカラック(Cayley-Bacharach)の定理」と呼ばれるものの特別な場合です(Cayleyは英国、Bacharachはドイツの数学者。いずれも19世紀)。ここで言う「3次曲線」とは、次の一般形で表される "3次曲線のすべて" であり、楕円曲線もその一部です。

[3次曲線の一般形]
ax3 + bx2y + cxy2 + dy3 + ex2 + fxy + gy2 + hx + iy + j = 0

10個の係数(=パラメータ)、 a b  ⋯  i j を決めると3次曲線が一つ決まります。もちろん、各係数を定数倍した曲線は同じ曲線です。つまり、この形の3次曲線の係数は実質的に "9次元" と言えます。3次曲線なので a b c d のうち少なくとも一つは 0 でないものがあります。その係数で全体を割れば、係数の数は9個になることからもわかります。

従って、一般には相異なる9点を通る3次曲線は一意に決まります。これは、直線の方程式を ax + by + c = 0 で表したとき、この式には3つのパラメータがあるものの実質的に2次元であって、相異なる2点を通る直線が一意に決まるのと同じことです。このことを踏まえると、命題 18.2 の前半である、

2つの3次曲線、 C1 C2 が相異なる9点、 P1 ,   P2  ⋯  ,   P9 を通るとする

のところについては、 P1 ,   P2  ⋯  ,   P9 何らかの制約条件がついているからこそ、2つの3次曲線が2つとも9点目の点を通るわけです。以上のことの裏返しは、

相異なる8点、 P1 ,   P2  ⋯  ,   P8 を通る3次曲線は一意に定まらず、無数にある

ということです。そして、さきほどの「相異なる8点を通る2つの3次曲線が2つとも9点目の点を通る」ということは、9点目が8点から決まる特別な点であることを示唆しています。そこで、相異なる8点を通る3次曲線が一般的にどういう式で表現できるかを考えます。8点の座標を、

P1 = x1 y1 P2 = x2 y2 P8 = x8 y8

とします。まず、3次曲線が P1 を通るということは、10個のパラメータは次の制約条件を満足しなければなりません。

x1 3 a + x1 2 y1 b + x1 y1 2 c + y1 3 d + x1 2 e + x1 y1 f + y1 2 g + x1 h +y1 i + j = 0

これは 10個の変数 aj についての線型方程式(1次方程式)なので、係数を変数の前に記述しました。同様にして、3次曲線が P2 から P8 を通ることから7個の制約条件が得られます。これらをまとめると、

{ x1 3 a + x1 2 y1 b +  ⋯  + y1 i + j = 0 x2 3 a + x2 2 y2 b +  ⋯  + y2 i + j = 0   ⋮ x8 3 a + x8 2 y8 b +  ⋯  + y8 i + j = 0  

の、合計8つの制約条件が得られます。8個の点を通る3次曲線の10個のパラメータは、この8つの制約条件(連立1次方程式)を満たさなければなりません。ということは、 10 - 8 = 2 で、これらのパラメータは、制約条件のない自由な2つのパラメータで表現できることになります。

たとえば ab を "2つのパラメータ" に選ぶと、残りの cj は、 αn a + βn b n=c  ⋯  j という「ab の1次式」で表現できます( αn βn は連立1次方程式の係数で決まる値)。しかしこれでは a=0 かつ b=0 のときに、すべてのパラメータが 0 という自明な解しか得られません。 x3 の項と x2y の項がない3次曲線はいくらでもありうるので、自明ではない解の中に a=0 b=0 となるものは当然あるはずです。つまり、 αn a + βn b の形は連立1次方程式の解の全部は表していません。

では、上記の連立1次方程式の「自明ではない解すべてを表す一般解」はどういう形でしょうか。それには8つの方程式を満たす独立な数値の組(=連立1次方程式の解)を2組用意します。つまり無数にある解の中から2つをピックアップし、それをベクトル表現で、

V 1 = a1 b1  ⋯  j1 V 2 = a2 b2  ⋯  j2

とします。"独立" とはこの場合、2つの数値群が異なった3次曲線を表現しているということです。そして、同時に 0 にはならない新たな2つのパラメータを導入します。それを λ1 ,   λ2 とすると、

λ1 V 1 + λ2 V 2

が連立1次方程式の一般解(不定解)になります。自由な2つのパラメータの1次式で表現されていて、8つの方程式を満たすことが明らかだからです。この一般解をもとに3次曲線の方程式を表現します。そこで、

f1 = a1 x3 + b1 x2y +  ⋯   ⋯  + h1 x + i1 y + j1

f2 = a2 x3 + b2 x2y +  ⋯   ⋯  + h2 x + i2 y + j2

の2つの関数を考えると、 f1 = 0 の3次曲線と f1 = 0 の3次曲線は、共に8点を通ります。従って、

λ1 f1 + λ2 f2 = 0

8点を通り、2つの自由なパラメータで表現された3次曲線群です。従って、これが P1 ,   P2  ⋯  ,   P8 を通るすべての3次曲線を表す一般形です。



以上を踏まえて命題 18.2 を検討します。命題を再掲すると、


2つの3次曲線、 C1 C2 が相異なる9点、 P1 ,   P2  ⋯  ,   P9 を通るとする。

別の3次曲線 D が 9点のうちの8点、 P1 ,   P2  ⋯  ,   P8 を通るとき、D P9 も通る。


でした。この前半の2つの3次曲線の関数式を

C1  :  F1 = 0 C2  :  F2 = 0

とします。 F1 = 0 F2 = 0 も9点、 P1 ,   P2  ⋯  ,   P9 を通る3次曲線です。従って F1 = 0 F2 = 0 P1 ,   P2  ⋯  ,   P8 8点を通る2つの3次曲線でもある。ということは、 P1 ,   P2  ⋯  ,   P8 の8点を通るすべての3次曲線は、

F = λ1 F1 + λ2 F2 = 0

で表されます。従って、命題の後半に出てくる別の3次曲線 D P1 ,   P2  ⋯  ,   P8 の8点を通るとすると、D F = λ1 F1 + λ2 F2 = 0 で表現できます。

ここでよく考えてみると、3次曲線 F = 0 は9点目の P9 を通るのでした。従って D P9 を通ります。これで 18.2 が成り立つことが証明できました。以上を振り返ってまとめると次のようになります。


・ 9つの点を通る3次曲線は一意に決まる。
・ 8つの点を通る3次曲線なら無数に存在する。
・ 8つの点を通る2つの3次曲線が、2つとも9つ目のある(特別な)点 P を通るとしたら、8点を通るすべての3次曲線は P を通る。



18.2 を踏まえて、楕円曲線の加法群で結合則が成り立つことを証明します。ポイントは「相異なる3つの直線を "3次曲線" として扱う」ことです。この扱いがなぜ可能かと言うと、3つの直線を、

f1 = a1x + b1y + c1 = 0 f2 = a2x + b2y + c2 = 0 f3 = a3x + b3y + c3 = 0

としたとき、

FL = f1 · f2 · f3 = 0 で表される2次元平面上の点の集合は3つの直線を表しているが、3次曲線の一般形である

からです。もちろん、 FL = 0 の3次曲線の一般形は、係数 a b  ⋯  i j に特別の関係があります。だからこそ3つの直線を表現しているわけです(数学用語で言うと "退化した" 3次曲線)。しかし特別の関係があるとしても 18.2 を証明した議論の筋道には全く影響しません。このことを踏まえて結合則を証明すべき図11を再掲します。

図K:結合則の検証.jpg
図11:結合則
「楕円曲線論入門」より引用


証明すべきことは 18.1 の、


P+Q R を結ぶ直線と、 Q+R P を結ぶ直線の交点を T とすると、楕円曲線は T を通る。


でした。図11で、

C1 : 点線の3直線から成る3次曲線
C2 : 実線の3直線から成る3次曲線

とすると、 C1 (点線) と C2 (実線)は次の9つの点を通ります。

P1 O
P2 P
P3 Q
P4 R
P5 P Q
P6 Q R
P7 P + Q
P8 Q + R
T P + Q R を結ぶ直線と、 Q + R P を結ぶ直線の交点

9つの点を通るのはそういう風に作図したからです。一方、楕円曲線は T 以外の P1 P8 の8点を通ります。8点は楕円曲線上の点として作ったからです。T だけは違って、楕円曲線上の点として作ったのではなく2直線の交点です。しかし 18.2 によって楕円曲線は T も通る。これで、楕円曲線上の有理点が作る加法群で結合則が成り立つことの証明が完成しました。



零元を無限遠点にとる加法群ではどうなるでしょうか。この場合は「射影平面での3次曲線」を考える必要があります。射影平面での3次曲線の一般形は、

[射影平面における3次曲線の一般形]
AX3 + BX2Y + CXY2 + DY3 + EX2Z + FXYZ + GY2Z + HXZ2 + IYZ2 + JZ3 = 0

ですが、証明の筋道は xy平面と全く同じです。というのも、証明のコアのところは「10変数の連立1次方程式(方程式数が8)の不定解が、一般形でどう表現できるか」であり、曲線方程式の未知数が xy の2つであっても XYZ の3つであっても証明の論理に影響がないからです。

というわけで、楕円曲線暗号で実際に使われる「無限遠点を零元にした加法群」においても結合則が成り立つのでした。


19. パスカルの定理


最後に余談ですが、18.2 から証明できる別の定理があります。「パスカルの定理」です。これはパスカルが16歳のときに発表した「円錐曲線試論」にあります。最も一般的な形で言うと次の通りです。

19.1  パスカルの定理

円錐曲線上に異なる6点、 P1 P6 をとる。

直線 P1 P2 P4 P5 の交点を Q1
直線 P2 P3 P5 P6 の交点を Q2
直線 P3 P4 P6 P1 の交点を Q3

とすると、 Q1 ,   Q2 ,   Q3 は同一直線上にある。


これは美しい定理です。どんな円錐曲線かを言っていないし(円、楕円、放物線、双曲線)、円錐曲線上の6点の位置も、その順序も何も言ってない。それにもかかわらず「同一直線上にある」という、シンプルで強い断定が結論にくる ・・・・・・。個人的経験を言うと、高校生時代にこの定理を知ってその "不思議さ" が印象的だったことを覚えています。

この定理の例を図15と図16、図17に示します。 Q1 P7 Q2 P8 Q3 T と書きました。円錐曲線が円か楕円であり、6点を円・楕円の周上に順に(= 一周するように)とった場合には、パスカルの定理は、

円・楕円に内接する6角形の対辺が作る2直線の交点3つは同一直線上にある

と簡潔に表現できます(図15)。

図O:パスカルの定理(1).jpg
図15 パスカルの定理(1)

図P:パスカルの定理(2).jpg
図16 パスカルの定理(2)
楕円上の点の位置は図15と同じだが名前付けが違う。しかし3点が同一線上に並ぶのは同じである。このように6点は楕円上のどの位置にどの順序で配置してもよい。

図Q:パスカルの定理(3).jpg
図17 パスカルの定理(3)

定理の証明は次の通りです。3次曲線、 C1 ,   C2 ,   D を、

C1 赤色の3次曲線
C2 青色の3次曲線
D P7 P8 を(T とは関係なく)結んだ直線と円錐曲線が作る、黒色の3次曲線

とします。 C1 C2 は 、 P1 P8 T を通ります。そういう風に作図したからです。一方、D P1 P8 を通ります。そうすると 18.2 より DT も通ります。D P7 P8 を通るように作図しましたが、T を通るようには作図していません。それでも T を通る。

その T は、D の円錐曲線部分にはありません。なぜなら、T は直線 P3 P4 上に(ないしは直線 P6 P1 上に)ありますが、円錐曲線と直線の交点は高々2つであり、 P3 ,   P4 が(ないしは P6 ,   P1 が)すでに円錐曲線上にあるからです。従って TD の直線部分にあるしかない。これで証明が終わりました。

パスカルの定理のよくある証明は、円の場合に補助円を用いて証明し、それを "斜めから見たら" 楕円でも成り立つ、とするものです。しかしこの定理は、すべての円錐曲線(=2次曲線の一般形、 ax2 + bxy + cy2 + dx + ey + f = 0 で表される曲線)で成り立つことが上の証明から分かります。



楕円曲線暗号は「楕円曲線上の有理点による加法群」の上に作られた暗号ですが、

楕円曲線上の有理点で加法群を構成できることと、パスカルの定理が成り立つことには、意外にも共通の数学的理由がある

のでした。




nice!(0) 

nice! 0