Comments
Description
Transcript
計算する立場からの楕円曲線論入門 目 次 - 九大数理学研究院
1 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 計算する立場からの楕円曲線論入門 The arithmetic of elliptic curves from a viewpoint of computation 横山 俊一1 （Shun’ichi Yokoyama） 九州大学大学院 数理学研究院 / JST CREST 講義のサポートページ 著者のウェブページにて, 講義概要や配布資料の電子版等を公開しています. 詳細は http://www2.math.kyushu-u.ac.jp/~s-yokoyama/Yamagata2014.html をご覧ください. K を体（例えば Q, C, Fp など）とする. このとき, これらを係数とする代数曲線（或いは代数曲 面）が定義され, 例えば代数幾何学ではその零点（f = 0 となる曲面上の点）の集合を追い求めるこ とが最重要課題となる. また同じ分野においても, 例えば「なめらかな曲線が大好きな人々」と「な めらかでない曲線が大好きな人々」に分かれ, それぞれが非常に豊かな数学を生み出していることも 珍しくない. さて, K 上の特別な 3 次曲線 E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 (ai ∈ K) のことを楕円曲線（elliptic curve）と呼ぶ. 楕円曲線は他の 3 次曲線とは一線を画している. 最近で は整数論の最先端への応用だけではなく, 我々の情報化社会を支える暗号技術やゲーム機の開発など にも用いられている. 実はその背後では, 楕円曲線特有の「ふしぎな性質」や「計算の難しさ」が鍵 となっている. 本稿（本講義）では, 学部で学ぶ代数学の基礎（群・環・体の基本的な性質）だけを仮定して, 楕 円曲線の豊穣な世界を覗き見ることを目指す. 実際に楕円曲線に「触れて」みるためには, 計算機を 用いた実験が有効である. そこで楕円曲線を実際に計算することを通して, 楕円曲線の持つ「ふしぎ な性質」や「計算の難しさ」を実感してもらいたい. 以後ほぼ全てのプログラム例を通じて, 無料の統合ソフトウェア Sage（セージ）を用いる2 . Sage は正式版のリリースが今から約 10 年前という, 比較的最近発足したプロジェクトであり, プログラミ ング初心者にもやさしい言語 Python（パイソン）をベースとして作られている. 本稿のもう一つの 目的として, この Sage に慣れ親しむことを目指す. 計算実習の時間も有効活用して欲しい. 目次 1 有理点をさがして 3 2 楕円曲線入門 5 3 最近の整数論の話題から 15 4 楕円曲線暗号入門 25 5 数式処理システムを用いた計算実習 33 5.1 5.2 1 2014 SageMath Cloud の利用法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pari/GP の利用法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 38 年 11 月 18 日改訂. お問い合わせ： [email protected] 計算機演習室の Windows マシンには Sage を直接インストール出来ない（仮想環境が必要である）. その為実習 では Sage のクラウドサービス SageMath Cloud を利用する予定である. しかしサーバの稼働状況により利用が困難な場 合は, Sage に含まれている数論システム Pari/GP（パリ・ジーピー）を単独利用する可能性もある. 詳細は 5 節を参照. 2 但し, 2 本資料について この講義資料は, 2014 年度後期・山形大学理学部数理科学科集中講義： • 数理情報特選 F（学部 4 年生が履修可能） • 数理科学特別講義 E（大学院修士学生が履修可能） の講義ノートです. 講義初回に出席者には 1 冊ずつ配付するほか, 講義のサポートページ http://www2.math.kyushu-u.ac.jp/~s-yokoyama/Yamagata2014.html に電子版（pdf ファイル）を置きます. 誤植等を見つけた方はぜひ横山までお知らせください. 速やかに改訂版 と差し替えます. この資料では, 敢えて幾つかの説明を省いた箇所があります. 例えばグラフ等の図解は一切載せていませ ん. これらについては講義で板書します. 即ち, 講義ノートを眺めながらただ話を聞いているだけではなく, きちんと板書をノートにとって内容を補完することが肝要となります. 細かい補足や, 巨大な数で板書に適 さないものなどは, 講義中では省略することもありますので, その際に本資料を役立てることにします. 単位を申請する学生さんへ この集中講義は 2 単位に相当します. 単位を申請する学生さんは, 講義初回（つまり今日）の指示をよく聞い ておいて下さい. 成績評価について, シラバスの内容を補足しておきます. • 目標は 演習問題 3.39, 3.40 が解けるようになること です. 24 ページを参照. • 成績は 平常点を x 点, レポート点を y 点としたとき 成績 = min {x + y, 100} 但し 0 ≤ x ≤ 40 と定めます. 部分的に欠席しても単位が得られるようになっていますが, 授業でお知らせした内容は全て 伝わっていると見なします. 情報は受講している友人などから随時仕入れておいて下さい. • 平常点は, 毎回の出席状況と計算演習での取り組みを評価します. 従って毎日出席をとります. 計算演習では, 実際に大学に備え付けのコンピュータを使って実習を行います. 初心者向けに行うので, 実 習開始時点で「計算機が苦手」「計算ソフトはほとんど使ったことがない」という心配は無用ですし, そ れが成績に影響することはありません. 一歩一歩確かめながら進めていくので, 楽しみながら実習に取り 組んで欲しいと思います. 詳細は 5 節をご覧下さい. • レポート点は, 講義終了後提出してもらう最終レポートでつけます. レポートの提出は, 単位を得るため の必要条件です（十分条件ではないことに注意！）. レポート課題 この資料にあるたくさんの「演習問題」を好きなだけ解いて提出して下さい. 解く問題 数は自由で, 配点は各演習問題の番号右に記載してあります. 但し, 演習問題の中には未解決問題も含まれています（番号横に明記してあります. 配点は記載されてい ません）. 意欲のある方は是非チャレンジして欲しいと思います. 内容に応じて（勿論, 解けてなくても） ボーナス点を差し上げます. • レポートの提出期限は, 授業期間中にお知らせする予定ですので, 指示に従って下さい. レポートは TEX や Word で作成しても, 手書きでも構いませんが, A4 用紙にプリントアウトしたもの or A4 用紙（ルーズリーフ可）に手書きしたもの を提出して下さい. 電子メイルでの提出は受け付けませんのでご注意下さい. また, レポートは複数枚に わたると思いますので, 必ず左上をステープラで留めて提出して下さい. 質問・相談等があれば, 遠慮なく授業中かその前後に仰って下さい. また, 横山のメイルアドレス [email protected] でも受け付けます. メイルを送られる際は, 件名に必ず氏名を明記して下さい（例： 「山形大の○○です」など）. メイルでの質問・相談は講義が全て終了した後でも構いません. 短い期間ですが, お互い楽しくがんばりましょう. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 1 3 有理点をさがして 楕円曲線の話題に入る前に, 有理点（rational point）について考察しよう. 有理点の計算は, 楕円 曲線の研究において最も重要な問題の一つである. f (x, y) を x, y の 2 変数多項式とし, f (x, y) = 0 を満たす点 (x, y) の集合（f = 0 の 解 とも言う）を調べる. 勿論, x, y ∈ R である. 定義 1.1. (x, y) は f (x, y) = 0 を満たすとする. x, y ∈ Q（共に有理数）のとき, (x, y) を有理点と 呼ぶ. 特に x, y ∈ Z（共に整数）のとき, (x, y) を整数点と呼ぶ. 例 1.2. f = 3x − y とする. このとき f = 0 を満たす点 (x, y) の集合をプロットすると, 直線 y = 3x となる. x が有理数ならば y も有理数となり, その逆も成り立つ. よって有理点は (t, 3t)（t ∈ Q）と なる. 一方整数点は (n, 3n)（n ∈ Z）となる. 従って有理点も整数点も無限個存在する. 直線の場合は非常に簡単である. では 2 次曲線の場合はどうだろうか？ 最も基本的な円の場合を 考えてみよう. 例 1.3. f = x2 + y 2 − 1 とする. このとき f = 0 を満たす点 (x, y) の集合をプロットすると, 円 x2 + y 2 = 1 となる. まずすぐに見つかるのは, 4 つの整数点 (±1, 0), (0, ±1) である. 実はそれ以外 には整数点は存在しない（実際にグラフを描いてみるとすぐ分かる）. では有理点はどのくらいあるかを調べてみよう. 今, 円上の点 (−1, 0) を通る傾き a の直線を描き, 円との交点を計算してみると と求まる. このとき a ∈ Q ならば ( 1 − a2 2a , 1 + a2 1 + a2 ) 1−a2 1+a2 2a ∈ Q かつ 1+a 2 ∈ Q なので, この交点は有理点となる. a ∈ Q の取り方は無限個あるので, 有理点は無限個存在することが分かる. ( ) 2 2a 補足 1.4. 上の例において, 実は有理点は 1−a の形のものしかないことが知られている. 1+a2 , 1+a2 では円の場合はいつでも同じく有理点が無限個見つかるだろうか？ — 答えは否である. 例 1.5. f = x2 + y 2 − 3 とする. このとき f = 0 を満たす点 (x, y) の集合をプロットすると, 円 x2 + y 2 = 3 となる. 実はこの場合, 有理点は一つも存在しない. 従って整数点も存在しない. これを 背理法で証明しよう. もし x2 + y 2 = 3 上に有理点が存在したとする. このとき m, n, r ∈ Z で gcd(m, n, r) = 1（最大 ( ) n 公約数が 1）となるものが存在し, (x, y) = m r , r と書ける. よって等式 m2 + n2 = 3r2 が成り立つ. ここで両辺を 3 で割った余りを考える. 3r2 ≡ 0（mod 3）であることは明らか. 一方左 辺は m2 ≡ 0 or 1, n2 ≡ 0 or 1 より m2 + n2 ≡ 0 となるためには m2 ≡ 0 かつ n2 ≡ 0 でなければ ならない. しかしこのとき m, n が共に 3 で割り切れてしまうので, 結局 r も 3 で割り切れてしまう. これは gcd(m, n, r) = 1（最大公約数が 1）であることに矛盾する. よって有理点が存在しないこと が証明された. 上の 2 つの例から分かる通り, 円上の有理点の多寡は半径を変えると大きく異なってくる. より一 般に x2 + y 2 = c（c ∈ N≥2 ）として, 有理点を持つような c はどのようなものかを調べてみよう. 演習問題 1.6 (5 点). 円 x2 + y 2 = c が有理点を持つことと, 円 x2 + y 2 = r2 c（r ∈ N）が有理点を 持つことは同値である. これを証明せよ. 実はより一般に r ∈ Q>0 でも成り立つ. 上の事実より, c は平方因子を持たない（square-free）として良い. 従って c = p1 p2 · · · pk （pi た ちは相異なる素数）と書ける. このとき次が成り立つ. 4 命題 1.7. 円 x2 + y 2 = c（c = p1 p2 · · · pk：相異なる素数の積）が有理点を持つ為の必要十分条件は, 全ての 1 ≤ i ≤ k に対して pi = 2 or pi ≡ 1（mod 4）が成り立つことである. 演習問題 1.8 (6 点). 円 x2 + y 2 = c が有理点を持つような c を 3 つ以上挙げ, それぞれについて具 体的に有理点を 1 つ以上見つけよ. 但し先に述べた c = 1, 3 は除く. それではいよいよ 3 次曲線の場合を考えてみよう. 3 次の場合は 2 次の場合よりもずっと複雑であ る. 一般に 3 次曲線と言ったら f = 0 (f = ax3 + bx2 y + cxy 2 + dy 3 + ex2 + gxy + hy 2 + ix + jy + k) で定義される曲線であって a, b, c, d のうち少なくとも 1 つは 0 でないものを指すが, 余りにも複雑な のでもっと簡単な例を考える. 例 1.9. f = x3 − y 2 − 2 とする. このとき f = 0 を満たす点 (x, y) の集合をプロットすると, 曲線 y 2 = x3 − 2 となる. この曲線上には有理点が無限個存在する. 例えば ( ) ( ) ( ) 129 383 164323 66234835 2340922881 113259286337279 (3, 5) , ,− , ,− , , , ··· 100 1000 29241 5000211 58675600 449455096000 などがある. 例 1.10. f = x3 − y 2 + 1 とする. このとき f = 0 を満たす点 (x, y) の集合をプロットすると, 曲線 y 2 = x3 + 1 となる. この曲線上の有理点（この場合全て整数点）は (−1, 0), (0, ±1), (2, ±3) の 5 個で, これで尽きている. 円の場合は, 有理点は無限個存在するか一つも存在しないかの何れかであった. 一方で上のような 曲線では, 有限個存在するというケースも出現する. このように具体的な曲線が与えられたときに, 有理点がどのくらい存在するかを決定することは非常に難しい問題である. 但し, もし有理点が一つ 見つかった場合は, その有理点を使って他の有理点を次々に見つけて行くテクニックが知られている. 実際にどうやって計算するのかについては次節で述べる. 演習問題 1.11 (C, 6 点). 例 1.9 の曲線 y 2 = x3 − 2 は, 有理点 ( ) 49680317504529227786118937923 11069550171650699467350859369161931440285365 ,− 3458519104702616679044719441 203392656460831967707109939312836961532761 を持つことを実際に確かめよ. 電卓では桁数が足りないと思われるので, 今回扱う Sage や Pari/GP 等の数式処理ソフトウェアの使用をお薦めする3 . なおこの問題を含め, 問題番号の右に (C) マーク のある問題を最終レポートとして提出する場合は, 数式処理システムでの出力結果を添付すること. Word や TEX にコピペしたり, 実行画面をキャプチャしたり, 様式は自由. 3 勿論, 手計算でも OK ですが・ ・ ・ 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 2 5 楕円曲線入門 楕円曲線は, 3 次曲線に幾つかの条件を課したものである. 定義の方法は複数あるが, ここでは最も 分かりやすい定義を述べる. 本稿を通じて K を体とする. 分かり易くするため, 例などは極力 K = Q の場合で考える. 実際には K は有限体や, 次のような代数体をよく用いる. 定義 2.1. Q の有限次拡大体を代数体（number field）と呼ぶ. さて, 3 次曲線 E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 (ai ∈ K) ) ( を考える4 . これを K 上の 3 次曲線と呼ぶ. K の標数が 2 でなければ, 変数変換 (x, y) 7→ x, y−a12x−a3 によって Ẽ : y 2 = 4x3 + b2 x2 + 2b4 x + b6 の形で書ける. 更に K の標数が 2 でも 3 でもない場合は (x, y) 7→ ( x−3b2 36 ) y , 108 によって E ′ : y 2 = x3 − 27c4 x − 54c6 の形で書ける. 例えば K = Q（標数 0）ならば必ずこの形に変形出来る. そのため, 予め簡易版 E ′ : y 2 = x3 + ax + b を考えることも多い（本稿でも時々扱う）. なお bi , cj 達は ak 達を用いて以下のように書ける. b8 は変数変換では使っていないが, すぐ後で用いる. b2 = a21 + 4a2 , b4 = 2a4 + a1 a3 , b6 = a23 + 4a6 , b8 = a21 a6 + 4a2 a6 − a1 a3 a4 + a2 a23 − a24 , c4 = b22 − 24b4 , c6 = −b32 + 36b2 b4 − 216b6 . ここで判別式と呼ばれる量を定義する. 定義 2.2. ∆(E) = −b22 b8 − 8b34 − 27b26 + 9b2 b4 b6 を E の判別式（discriminant）と呼ぶ. これを用いて 楕円曲線 を以下のように定義する. 定義 2.3. ∆(E) ̸= 0 のとき, E は K 上の楕円曲線（elliptic curve）であると言う. K = Q のとき, ∆(E) ̸= 0 は楕円曲線のグラフに特異点が現れない（＝なめらかな）状態を意味す る. ∆(E) = 0 ならば必ず特異点を持つ. 補足 2.4. 楕円曲線とは, 所謂「楕円」のこと ではない5 . 楕円関数論, 特に楕円積分を行う際にこの ような式が現れることから, この名前が付いている. 補足 2.5. 判別式は, 楕円曲線の不変量ではない. 同型（後で定義する）な楕円曲線であっても判別 式が異なる場合がある. 4 係数のインデックスがばらばらで, しかも a を飛ばして a になっているが, これは慣例で誤植ではない. 気持ち悪いか 5 6 もしれないが, 我慢しよう. 5 高校数学で, 楕円は x2 a2 + y2 b2 = 1（a, b ∈ R）で表せることは勉強したはず. 6 補足 2.6 (C 上の楕円曲線). 本稿では扱わないが K = C（複素数体）上の場合, 楕円曲線は C/Λ（Λ は 2 次元格子）と同型となり, トーラス（ドーナツの表面）と見なすことが出来る. 演習問題 2.7 (5 点). E ′ : y 2 = x3 + ax + b について ∆(E ′ ) を計算せよ. 特異点は 2 種類存在する. 一つは y 2 = x3 のように尖った部分に現れるもので, これをカスプ（cusp） と呼ぶ. もう一つは y 2 = x3 + x2 のように自己交叉（この場合原点で交叉する）を持つもので, こ れをノード（node）と呼ぶ. ∆(E) = 0 のとき, 特異点がどちらのタイプであるかを判定する方法が 存在する. 命題 2.8. ∆(E) = 0（特異点を持つ）と仮定する. このとき, 特異点がカスプ型であるための必要十 分条件は c4 = 0 である. また, 特異点がノード型であるための必要十分条件は c4 ̸= 0 である. 演習問題 2.9 (12 点). E または E ′ において, 楕円曲線にならない例を（上の 2 つの曲線以外に）カ スプ型とノード型, それぞれ 1 つずつ挙げよ. またその特異点（自己交叉点）を決定せよ. それでは, ここまでの内容を Sage を使って復習しよう. まず Q 上の楕円曲線を Sage 上で定義 する. sage: E=EllipticCurve([1,2,3,4,5]); E E は楕円曲線 y 2 + xy + 3y = x3 + 2x2 + 4x + 5 のことである. Sage では 5 つの有理数係数 a1 , a2 , a3 , a4 , a6 を順番に入力すれば, Q 上の楕円曲線が定義される. セミコロン ; はここで一命令 を終了し, 次の命令に移るためのサインである. E と書けば, 定義した楕円曲線の情報が Elliptic Curve defined by y^2 + xy + 3y = x^3 + 2x^2 + 4x + 5 over Rational Field と出力される. 因みに簡易版 E ′ : y 2 = x3 + ax + b を扱いたい場合は sage: E=EllipticCurve([a,b]); E とすれば良い（a,b に係数が入る）. 他にも Cremona’s index と呼ばれるラベルを使って呼び出すこ とも出来るが, ここでは省略する（後で補足する）. さて, 判別式を計算するためには bi 達を先に計算しておく必要があったが, これは非常に面倒であ る. 幸運なことに Sage には判別式を一発で計算する関数 discriminant が存在する. sage: E.discriminant() と書けば, E の判別式を計算してくれる. 因みに Sage の関数の多くはこのように後ろに付けて記述 する. 空白の括弧の中には必要に応じてオプションを追加する. 何も書かなければデフォルトの設定 が適用されるので, 大抵の場合は空白で問題ない. さて判別式を計算することは出来たが, 特異点がカスプ型かノード型かを判定するには c4 の計算 が必要であった. 実は Sage ではこのまま sage: E.c4() と書けば良い. 他の bi 達も同様である. 楕円曲線のグラフを描くことも簡単である. プロット関数 sage: E.plot() を実行すれば, 無圧縮 png ファイルとしてグラフが出力される. また必要に応じて pdf 形式で出力 することも可能である6 . 6 余談：つい最近までは, 数学の論文を書く際に図を入れたい場合には eps 形式と呼ばれるフォーマットに変換して貼り付 ける方法がほとんどであったが, 最近では pdf 形式に変換して貼り付ける方が主流になりつつある. 確かに解像度のロスも少 ないので, 数年後には eps 形式は使われなくなるかもしれない・ ・ ・かも. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 7 演習問題 2.10 (C, 但し手計算でも可, 9 点). 次の 3 つの楕円曲線の判別式を計算し, グラフを描け. 1. y 2 = x3 − 3x + 3 2. y 2 = x3 + x 3. y 2 = x3 − x それでは, 1 節で学んだ有理点について楕円曲線上で考察してみよう. 楕円曲線には顕著な特徴と して, 1 つ有理点が与えられたとき, そこから次々と新しい有理点を作り出すことが可能となってい る. 新しい有理点は無限個見つかる場合もあれば, 途中から同じ有理点に戻ってしまい有限個しか見 つからない場合もある. これは楕円曲線上の点に関する加法（足し算）と整数倍で表現出来る. まず はこれを定義する. 定義 2.11. E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 上の点 P = (x1 , y1 ), Q = (x2 , y2 ) に対し て, 次のように演算を定義する： • −P = (x1 , −y1 − a1 x1 − a3 ), • P + Q = (x3 , −(λ + a1 )x3 − ν − a3 ), 但し x3 = λ2 + a1 λ − a2 − x1 − x2 . また λ, ν は以下のように定める： • x1 ̸= x2 のとき, λ = y2 − y1 y1 x2 − y2 x1 ,ν= , x2 − x1 x2 − x1 • x1 = x2 のとき, λ = 3x21 + 2a2 x1 + a4 − a1 y1 −x31 + a4 x1 + 2a6 − a3 y1 ,ν= . 2y1 + a1 x1 + a3 2y1 + a1 x1 + a3 更に, 整数倍を nP = P + P + · · · + P （n 個の和）で定義する. 最後に無限遠点 O を導入する. 演習問題 2.12 (6 点). 上に従い, E ′ : y 2 = x3 + ax + b 上の点に対して加法公式, 2 倍公式を書け. この議論は, 実際に図を描くとすっきりする. 任意の楕円曲線と直線は必ず 3 点で交わり, これら を P, Q, R とすれば P + Q + R = O が成り立つ.「無限遠点」の由来は P + (−P ) = O を図示して みると良い（第 3 の交点はどこにあるだろうか？）. 命題 2.13. 上で定めた加法により, E ∪ {O} はアーベル群（可換群）をなす（このとき無限遠点 O は単位元となる）. 特に, この加法は有理点に関して閉じており, やはり E 上の有理点全体もアーベ ル群をなす. なお取り決めとして O も有理点と見なしている. 定義 2.14. E を K 上の楕円曲線とするとき, E 上の有理点全体を E(K) と書きモーデル・ヴェイユ 群（Mordell-Weil group）と呼ぶ. 定理 2.15 (Mordell-Weil). E(K) は有限生成アーベル群である. 即ち E(K) ≃ Z⊕r ⊕ G と書ける. 但し G は有限群である. G は E(K) のねじれ部分（torsion part）なので, 以降 E(K)tors と書くことにする. 定義 2.16. 定義 2.15 において, r を楕円曲線 E の階数（ランク, rank）と呼ぶ. E(K) の構造を求めることは, 楕円曲線の計算において最も重要な問題の一つである. このうち Z⊕r の計算法は 3 節で詳しく扱うことにして, 先に E(K)tors の計算について述べる. 実は K = Q の場合 は完全に決定されている. 8 定理 2.17 (Mazur7 , 1977). E(Q)tors は次の何れかと同型である. m ∈ Z とする： • Z/mZ, 但し 1 ≤ m ≤ 12, m ̸= 11, • Z/2Z ⊕ Z/2mZ, 但し 1 ≤ m ≤ 4. K の拡大次数が小さい場合にも幾つか結果が知られているが, 一般にはほとんど決定されていない. √ 例えば二次体 K = Q( 5) 上の楕円曲線 E : y 2 + xy + y = x3 + x2 − 3x + 1 を考えると E(K)tors ≃ Z/15Z となり, Mazur の定理では現れないような場合が登場する. しかし, 与えられた楕円曲線に対して E(K)tors を計算する場合は, 効率的なアルゴリズムが存在する. 演習問題 2.18 (C, 8 点). 楕円曲線 E : y 2 = x3 + 2x + 3 に対し, E(Q) ≃ Z ⊕ Z/2Z である. 即ち E のランクは 1 である. 次を確かめよ. 1. E 上の点 P = (−1, 0) の位数は 2（i.e. 2P = O）であることを確かめよ. 2. E 上の点 Q = (3, −6) は無限位数, 即ち任意の n ∈ N に対して nQ ̸= O であることを確かめ よ.（ヒント：Mazur の定理を用いよ） 実際 P, Q は E(Q) の生成元であることが知られている. なお n ≥ 2 でないことを証明するにはも う少し高度な議論が必要である. 続いて, 2 つの楕円曲線 E1 , E2 が与えられたとき, それらが「同じ曲線か否か」を判定する方法を 与えよう. 最も簡単なものは同型であるか否かであるが, もう少し弱めて同種という概念を定義する. 同型という概念はこの延長線上にある. 定義 2.19. 楕円曲線 E1 から E2 への写像 ϕ : E1 → E2 が次を満たしているとする： 1. P = (x, y) ∈ E1 に対し, ϕ(P ) ∈ E2 の各座標が x, y の有理式で書ける. 2. P, Q ∈ E1 に対し, ϕ(P + Q) = ϕ(P ) + ϕ(Q). 即ち ϕ は加法に関する準同型写像である. このとき ϕ を E1 の同種写像（isogeny）であると言う. 別の言い方をすると, E1 と E2 は同種であ ると言う. 同種という概念は, 楕円曲線の「同じ族」を見つけ出す際に重要である. 楕円曲線の研究において は “同種を除いて”（up to isogeny）という議論が良く用いられる. 定義 2.20. 同種写像 ϕ が更に全単射であるとき, ϕ は同型写像であると言う. 従って E1 と E2 の間 に同型写像が存在するとき, E1 と E2 は同型であると言い, E1 ≃ E2 と書く. 特に基礎体 K が代数閉体であるとき, 同型か否かを簡単に判定出来る不変量が存在する. ここで定 義 2.2 で学んだ判別式を用いる. 定義 2.21. j(E) = c34 (4a)3 （E ′ の場合は j(E ′ ) = −1728 ）を E （または E ′ ）の j 不変量 ∆(E) ∆(E ′ ) （j-invariant）と呼ぶ. 命題 2.22. K を K の代数閉包とする. E1 ≃ E2 （K 上同型）と j(E1 ) = j(E2 ) は同値である. 7 15 個に限る, という予想そのものは Ogg（1975）による. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 9 演習問題 2.23 (6 点). j0 ̸= 0, 1728 とし、楕円曲線 E : y 2 + xy = x3 − を考える. このとき ( ∆(E) = 36 1 x− j0 − 1728 j0 − 1728 j0 j0 − 1728 )3 , j(E) = j0 であることを示せ. 因みにこれは Tate の族 と呼ばれる楕円曲線である. それでは再び計算演習に移る. まずはモーデル・ヴェイユ群 E(Q) を実際に計算してみよう. E と して y 2 + y = x3 + x2 − 2x を選ぶ8 . sage: E=EllipticCurve([0,1,1,-2,0]) sage: E.gens() [(-1:1:1), (0:0:1)] 出力された生成元は 2 つで, 射影座標で表記されている9 . 実際に (−1, 1) と (0, 0) は無限位数であ り, 独立した生成元である. よって E のランクは 2 以上であることが分かった. 実はこの曲線のランクは 2 であり, これで全て求まったことになる. このように Q 上の楕円曲線 の場合は, 最近の計算機の進歩もありかなり正確に生成元が求まる. しかしながら一般の K の場合 は（拡大次数の低い代数体であっても）依然として難しく, 論文になるレベルの問題が幾つも残って いる. さて, 先程の E のランクは 2 であった. では Q 上の楕円曲線でランクが 3 のものは存在するだろ うか？ — 答えは yes で, sage: E=EllipticCurve([0,0,0,-82,0]) sage: E.gens() を実行すれば確かめることが出来る. ランクが 4 のものは sage: E=EllipticCurve([0,-1,0,-24649, 1355209]) sage: E.gens() などがある. この調子で, 次のような予想が考えられる. 予想 2.24. 任意の n ∈ N が与えられたとき, ランクが n の Q 上の楕円曲線を少なくとも 1 つ構成出 来る. つまり, 幾らでもランクの大きな Q 上の楕円曲線を構成することは可能である. この予想は現在も未解決のままである. 現時点での世界記録は Elkies による n = 28 である. 曲線 E は次で与えられる： E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 a1 = 1 a2 = −1 a3 = 1 a4 = 20067762415575526585033208209338542750930230312178956502 a6 = 34481611795030556467032985690390720374855944359319180361266008296291939448732243429 8 これは Cremona’s index 389a と呼ばれるものである. 389 は導手（conductor, 後で定義する）であり, a は同種なも の全てに対して付けられた index である. 2 つ以上あれば b, c, · · · と続く. 9 射影座標については講義で補足するが, 第 3 成分が 1 の場合は, 第 1 成分が x 座標, 第 2 成分が y 座標を表していると 考えて良い. 10 28 個の生成元は以下の通り： P1 = (−2124150091254381073292137463, 259854492051899599030515511070780628911531) P2 = (2334509866034701756884754537, 18872004195494469180868316552803627931531) P3 = (−1671736054062369063879038663, 251709377261144287808506947241319126049131) P4 = (2139130260139156666492982137, 36639509171439729202421459692941297527531) P5 = (1534706764467120723885477337, 85429585346017694289021032862781072799531) P6 = (−2731079487875677033341575063, 262521815484332191641284072623902143387531) P7 = (2775726266844571649705458537, 12845755474014060248869487699082640369931) P8 = (1494385729327188957541833817, 88486605527733405986116494514049233411451) P9 = (1868438228620887358509065257, 59237403214437708712725140393059358589131) P10 = (2008945108825743774866542537, 47690677880125552882151750781541424711531) P11 = (2348360540918025169651632937, 17492930006200557857340332476448804363531) P12 = (−1472084007090481174470008663, 246643450653503714199947441549759798469131) P13 = (2924128607708061213363288937, 28350264431488878501488356474767375899531) P14 = (5374993891066061893293934537, 286188908427263386451175031916479893731531) P15 = (1709690768233354523334008557, 71898834974686089466159700529215980921631) P16 = (2450954011353593144072595187, 4445228173532634357049262550610714736531) P17 = (2969254709273559167464674937, 32766893075366270801333682543160469687531) P18 = (2711914934941692601332882937, 2068436612778381698650413981506590613531) P19 = (20078586077996854528778328937, 2779608541137806604656051725624624030091531) P20 = (2158082450240734774317810697, 34994373401964026809969662241800901254731) P21 = (2004645458247059022403224937, 48049329780704645522439866999888475467531) P22 = (2975749450947996264947091337, 33398989826075322320208934410104857869131) P23 = (−2102490467686285150147347863, 259576391459875789571677393171687203227531) P24 = (311583179915063034902194537, 168104385229980603540109472915660153473931) P25 = (2773931008341865231443771817, 12632162834649921002414116273769275813451) P26 = (2156581188143768409363461387, 35125092964022908897004150516375178087331) P27 = (3866330499872412508815659137, 121197755655944226293036926715025847322531) P28 = (2230868289773576023778678737, 28558760030597485663387020600768640028531) 実はこの結果は「互いに独立な生成元が 28 個見つかった」という主張であって, 29 個目が存在す るか否かはまだ未解決である. 演習問題 2.25 (C, 未解決問題！). Elkies の E のランクは真に 28 であるか否かを解決せよ. 即ち n = 28 と主張するならばそれを証明し, n ≥ 29 と主張するならば, 新たな生成元を見い出せ. 演習問題 2.26 (未解決問題！). 予想 2.24 を解決せよ. これが出来たら超有名人になれます. 一方, 基礎体 K を動かすことを許せば, 幾らでもランクの大きな楕円曲線を構成することが可能で ある. √ √ √ 定理 2.27 (Kida). E : y 2 = x3 − x を Km = Q( p1 , p2 , · · · , pm ) 上の楕円曲線とする. pi は相 異なる素数で pi ≡ 5 or 7（mod 8）と選べば, m を増やして E のランクを幾らでも大きく出来る. 続いて j 不変量を計算する. Sage ではそのまま sage: E=EllipticCurve([0,0,1,-1,0]) sage: E.j_invariant() 110592/37 とすれば求められる. 演習問題 2.28 (C, 6 点). 楕円曲線 E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 の j 不変量を求め よ. これは手計算ではかなりしんどいと思うので, 計算機専用問題とする. ヒント：Sage で一般係数を含む楕円曲線を定義するには次のようにすれば良い. sage: var(’a,b’); E=EllipticCurve([a,b]) 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 11 さて, E(Q)tors の計算はどんなアイデアで行われているのかを考察する. アルゴリズム論的に は Schmitt の手法などが知られているが, ここでは割愛する. 簡単のため, 楕円曲線は E : y 2 = x3 + a2 x2 + a4 x + a6 （即ち a1 = a3 = 0）としよう. ここでは次に挙げる定理が重要となる. 定理 2.29 (Lutz-Nagell). E の係数 a2 , a4 , a6 は全て整数であるとする. このとき, P = (x1 , y1 ) ∈ E(Q)tors ならば x1 , y1 は共に整数となる. 命題 2.30. 上の状況で, P = (x1 , y1 ) ∈ E(Q)tors ならば y1 = 0 or y12 | ∆0 が成り立つ. ここで ∆0 = 27a26 + 4a32 a6 + 4a34 − a22 a24 − 18a2 a4 a6 であり, 判別式との間には関係式 ∆ = −16∆0 が成り立つ. これを使うと, 例えば 楕円曲線 E : y 2 = x3 − 43x + 166 の場合 E(Q)tors ≃ Z/7Z が示せる. 演習問題 2.31 (C, 12 点). 上の下線部を, 以下の誘導に従って示せ. 1. ∆0 を計算せよ. 2. E(Q)tors の元（但し無限遠点 O は除く）となりうるのは {(3, ±8), (−5, ±16), (11, ±32)} の 6 点のみであることを示せ. 3. このうち, 例えば点 (3, 8) は E(Q)tors の生成元となることを示せ. これにより, 2. の点は全て (3, 8) の整数倍で書けることが分かり, E(Q)tors ≃ Z/7Z が導かれる. それでは, 本節の最後の話題として楕円曲線の還元と導手を定義する. 特に導手は j 不変量と並ん で楕円曲線の重要な不変量である. ここからは簡単のため, K = Q の場合のみを考える. 楕円曲線 E の係数が全て整数であるとき, それらを全て mod p して考える（Fp の元として考える） ことが出来る. これが 4 節で取り扱う有限体上の楕円曲線である. このとき E 上の点は (x, y) ∈ Fp ×Fp なので, グラフを描くと離散的（discrete）な点集合となってしまう. そのため直感的には「特異点が 無い」 「なめらか」という感じがせず気持ち悪いかもしれない. そこでここは数学的に, 定義 2.3 から ∆(E) ∈ Fp − {0} ならば E を Fp 上の楕円曲線と見なすことにしよう. 定義 2.32. E を Q 上の楕円曲線で, 係数が全て整数であるもの： E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 (ai ∈ Z) とする. この係数を単に mod p したもの： Ep : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 (ai ∈ Fp ) を, E の p における還元（reduction at p）と呼ぶ. Ep はいつも楕円曲線になる（i.e. ∆(Ep ) ̸= 0）とは限らない. 正確には, p が判別式 ∆(E) を割り 切るような素数を選んでしまうと ∆(Ep ) = 0 となる. そこで, 還元しても楕円曲線であり続ける場 合, これを “良い還元” と呼ぶことにしよう. 12 定義 2.33. Ep が Fp 上の楕円曲線となる（i.e. ∆(Ep ) = ̸ 0）とき, E は p で良い還元を持つ（has good reduction at p）と呼ぶ. 逆に Ep に特異点が出現し, Fp 上の楕円曲線でなくなる（i.e. ∆(Ep ) = 0） とき, E は p で悪い還元を持つ（has bad reduction at p）と呼ぶ. 補足 2.34. 上の状況で, それぞれの p を「良い素数/悪い素数」（good prime/bad prime）と呼ぶこ ともある. ∆(E) の素因子のリストは, 悪い素数のリストに一致する. 更に, 悪い還元のときには Ep に特異点が出現するが, その特異点には 2 種類あったことを思い出 そう（命題 2.8 及びその直前の文脈. c4 が 0 か否かでノード型かカスプ型に分かれるのであった）. そのため, 悪い還元を更に 2 つに分類する. 定義 2.35. E が p で悪い還元を持つとする. Ep がノード型の特異点を持つとき, E は p で乗法的 （半安定）還元を持つ（has multiplicative (semistable) reduction at p）と呼ぶ. Ep がカスプ型の特 異点を持つとき, E は p で加法的（不安定）還元を持つ（has additive (unstable) reduction at p）と 呼ぶ. これを用いて導手を定義する. 判別式が「悪い素数のリスト」を与えていたのに対し, 導手は「悪 い素数のリスト＋還元の様子」を与えており, しかも不変量となる. 定義 2.36. E を Q 上の楕円曲線とする. このとき ∏ N (E) = pfp (E) p : prime を E の導手（conductor）と呼ぶ. E ≃ E ′ なら N (E) = N (E ′ ) である. fp (E) は次で定める： • E が p で良い還元を持つとき fp (E) = 0, • E が p で乗法的還元を持つとき fp (E) = 1, • E が p で加法的還元を持つとき fp (E) = 2 + δp . δp は depth of wild ramification と呼ばれる 0 以上の整数で, 特に p ̸= 2, 3 ならば δp = 0 である. 補足 2.37. p = 2, 3 のとき, fp (E) の上界は f2 (E) ≤ 5, f3 (E) ≤ 3 であることが知られている. よって導手は, 1) ∆(E) を計算し, その素因子の集合を BE として保持する, 2) 各 p ∈ BE に対し, c4 を計算することで fp (E) を計算する, 3) pfp (E) を全て掛け合わせる, という 3 ステップで計算出 来る. Sage ではこれを一発で計算出来るようになっている. sage: E.conductor() 演習問題 2.38 (C, 但し手計算でも可, 5 点). Q 上の楕円曲線 E : y 2 + xy + 3y = x3 + 2x2 + 4x + 5 に対し, 上の 3 つのステップに沿って N (E) を計算せよ. また可能ならば Sage の関数 conductor を用いて, 計算結果が正しいかどうか確かめよ（＋ 3 点）. 定義から分かる通り, N (E) ≥ 1 である. 特に N (E) = 1 のときは, 全ての p に対して E が良い還 元を持つことを意味する. これには特別な名前が付いている. 定義 2.39. Q 上の楕円曲線 E に対し N (E) = 1 のとき, E は至る所良い還元を持つ（everywhere good reduction）と言う. また, 悪い素数を意識して次のような表現も使う. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 13 定義 2.40. Q 上の楕円曲線 E に対し, 悪い素数の集合を BE とする. このとき E は BE の外で至る 所良い還元を持つ（everywhere good reduction outside BE ）と言う. 特に悪い素数が p 一つしかな いときは「p の外で至る所良い還元を持つ」などと言う. 実は, Q 上の楕円曲線はどのように選んでも, 必ず 1 つ以上の悪い還元を持ってしまうことが知ら れている. 正確な出自は諸説あるが, 恐らく最初は Tate によるものと思われる. 定理 2.41 (Tate). Q 上至る所良い還元を持つ楕円曲線は存在しない. 演習問題 2.42 (C 及び手計算, 16 点). 定理 2.41 を, 以下の手順に従って証明せよ. E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 (ai ∈ Z) 1. 等式 ∆(E) = c34 − c26 を示せ. 1728 2. E が Q 上至る所良い還元を持つと仮定する. このとき ∆(E) = ±1 となることを示せ. 3. 関係式 c26 = c34 ± 1728 は 2 種類の楕円曲線と見なすことが出来る. (c4 , c6 ) の候補, 即ちこの楕 円曲線の整数点（この方程式の整数解とも言える）を全て求めよ. 4. 3. で求めた (c4 , c6 ) からは ai ∈ Z 達は復元出来ない（即ちこれらは (c4 , c6 ) とはなり得ない） ことを証明せよ. ヒント： E は y 2 = x3 − 27c4 x − 54c6 と同型であることを用いよ. 基礎体が K （̸= Q）の場合でも還元と導手を同様に定義出来るが, この場合 mod p という概念は √ 相容れない（例えば “ −5 mod p” は意味を持たない）. これを乗り越えるため, K 上の楕円曲線に おいては, その整数環 OK の素イデアル p を用いて, 係数を mod p して考える. 従って導手も（悪い 還元を持つような）素イデアルの積として与えられ, それが一つもない場合（導手が自明なイデアル (1) となる場合）を K 上至る所良い還元を持つと定義する. Q 上の場合とは異なり, K 上至る所良い 還元を持つ楕円曲線は存在する. このような楕円曲線を（体系的かつ具体的に）沢山見つけようとい う方面の研究も最近進んでいる. 演習問題を残しておく. 興味のある方は是非適宜自学するなどしてチャレンジして頂きたい. 演習問題 2.43 (20 点). K を Q でない代数体とする. その整数環を OK と書き, その素イデアル p を一つとって固定する. E を K 上の楕円曲線とする. 1. E の p における還元（reduction at p）の正確な定義を述べよ. 2. E の導手 N (E) の正確な定義を述べよ. 但し depth of wild ramification に関する定義は不要. √ √ 演習問題 2.44 (C, 20 点). K = Q( 6) とし, 基本単数は ε = 5 + 2 6 をとる. 2 つの楕円曲線 E1 : y 2 = x3 − 4(2 + √ 2 6)x + 4εx , E2 : y 2 + √ √ 6xy − y = x3 − (2 + 6)x2 を考える. 次の問いに答えよ. 1. E1 に対して c4 , c6 , ∆(E1 ), j(E1 ) を計算せよ. 2. E2 に対して c4 , c6 , ∆(E2 ), j(E2 ) を計算せよ. 3. E1 , E2 はどちらも至る所良い還元を持つ楕円曲線であることを証明せよ10 . 10 実は E1 ≃ E2 であり, 特に E2 は大域極小モデル（global minimal model）と呼ばれている. 14 √ 演習問題 2.45 (8 点). Q( 3 28) 上の楕円曲線 E : y 2 + a1 xy + a3 y = x3 (a2 = a4 = a6 = 0) √ を考える. ∆(E) = a33 (a31 − 27a3 ) であることを用いて, E が Q( 3 28) 上至る所良い還元を持つよう な (a1 , a3 ) を 1 つ定めよ. 演習問題 2.46 (C, 未解決問題！). この問題は, 本稿の著者による 2 編の論文11 に基づく. この研究 の動機の一つは, 加川貴章氏（立命館大学）及び木田雅成氏（東京理科大学）の先行研究である. √ √ 今, K を二次体 Q( ±m)（m > 0: 平方因子無し）又は純三次体 Q( 3 m)（m > 0: 立方因子無し） とする. この論文において考えている問題は K を一つ固定し, K 上至る所良い還元を持つ楕円曲線を（全て）決定せよ. もし存在しない場合は, それを証明せよ. というものである. 但し「全て決定する」という部分を攻略するには同種な楕円曲線を精密に調べる 必要があるので, ここでは単に「何でも良いからとにかく見つける」「部分的に非存在を示す」こと が出来ればそれで十分とする. 現時点でのデータベースは http://www2.math.kyushu-u.ac.jp/~s-yokoyama/ECtable.html に纏められている. これを基に, 次の問題に挑戦してみよ. √ 1. K = Q( m) 上の場合において, 1 < m < 100 の範囲で未解決なものは m = 26, 51, 79, 86, 87, 91 である. これらの場合を解決せよ. 但し, 記号は次のように読む. • PEX/UNDET 至る所良い還元を持つ曲線は少なくとも 1 つ見つかっているが, それで全て かどうかは未解決. • PNEX/UNDET 現時点で, 至る所良い還元を持つ曲線は 1 つも見つかっていない. 全く存 在しないかどうかは未解決. √ 2. K = Q( −m) 上の場合において, 1 < m < 100 の範囲で未解決なものは m = 38, 53, 61, 89 である. これらの場合を解決せよ. √ 3. K = Q( 3 m) 上の場合において, 1 < m < 100 の範囲で未解決なものはたくさんある（最も小 さいものは m = 23）. これらについても解決を試みよ. なお, 最近統一的な結果が津田塾大学の筒石奈央氏により与えられた. これを用いると, 三次体の場 合において幾つかの進展が見られる. 但し次の問題に関しては残念ながら進展が見込めていない. √ 4. K = Q( 3 46) の場合を考える. 現在, 著者（横山）によって至る所良い還元を持つ楕円曲線が 1 本だけ構成されている（脚注12 参照）. それ以外に存在するか否かを決定せよ. 11 1. “Non-existence of elliptic curves with everywhere good reduction over some real quadratic fields”, Journal of Math-for-Industry 3 (2011), pp.113-117.（島崎有氏と共著） 2. “On elliptic curves with everywhere good reduction over certain number fields”, American Journal of Computational Mathematics 2, No.4 (2012), pp.358-366. 12 y 2 + √ 3 √ 3 46xy + √ 462 + 3 46+1 y 3 C1 = √ = x3 + ( 3 46 + 1)x2 + C1 √ 3 √ 462 +C2 3 46+C3 x 3 + C4 √ 3 √ 462 +C5 3 46+C6 . 3 94219593757433390681493864706, C2 = 1081334709186632184731947617604, C3 = 5084087035543830437128808550119, C4 = 23258423334479295709473275474986025640457867, C5 = 827892116462926667504946133778759990377913857, C6 = 3264974121115333449055262059201401614426686175. 但し係数は： 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 3 15 最近の整数論の話題から ここからは, 最近の整数論の流行を含めてやや進んだ内容を紹介する. 本稿では特に楕円曲線の有 理点の計算, 即ちモーデル・ヴェイユ群 E(K) の計算に関連した話題を扱う. そこでまず, 2 節で後 回しにしていた E(K) の自由部分（Z⊕r ）の計算について述べる. まず突然ではあるが, 次の完全系 列を考える. 少し難解な概念が登場するが, 気にせずざっと読み進めて頂いて構わない. 定理 3.1. E, E ′ を K 上の楕円曲線とし, ϕ : E → E ′ を零でない同種写像とする. このとき次のよ うな完全系列が存在する. 0 → E ′ (K)/ϕ(E(K)) → Selϕ (E/K) → III(E/K)[ϕ] → 0 特に Selϕ (E/K) は有限群となる. 定義 3.2. 上に登場している Sel(E/K) を E のセルマー群（Selmer group）と呼ぶ. また III(E/K) をテイト-シャファレヴィッチ群（Tate-Shafarevich group）と呼ぶ13 . 上の 2 つの群は, 同種写像と K の絶対 Galois 群 Gal(K/K) からなる 1 次元 Galois コホモロジー と, ヴェイユ-シャトレ群（Weil-Châtelet group）と呼ばれる特別な群を用いて定義される. ここで 解説するには予備知識が不足しているので, 詳細は割愛する. 特に同種写像が m 倍写像ならば, 上の 完全系列は 0 → E(K)/mE(K) → Selm (E/K) → III(E/K)[m] → 0 と書ける. 但し III(E/K)[m] = {t ∈ III(E/K) | mt = 0}（m-torsion）である. ここで我々が求め たいのは E(K)/mE(K) であるが, これを直接求めることは非常に困難である. そこで, 完全系列の 「お隣さん」の情報をうまく使って求めようという発想である. 特に m = 2 のとき, 埋め込み E(K)/2E(K) ,→ Sel2 (E/K) によって, E のランクを Sel2 (E/K) を用いて上から評価することが出来る. これを 2-descent 法と呼ぶ. descent 法そのものは一般の m ≥ 2 に対して定義出来るので m-descent 法と呼ばれるが, 実用上は 2-descent 法が最もよく用い られる. 更に III(E/K)[2] が計算出来れば, E(K)/2E(K) を決定出来る. 言いかえれば, III(E/K)[2] は E(K)/2E(K)（直接計算出来ない）と Sel2 (E/K)（直接計算出来る）の誤差を表す量と言える. しかし残念なことに, III(E/K)[2] の計算は猛烈に困難である. 更に, 理論的にもこの群の構造はほと んど分かっていない. 予想 3.3. III(E/K) は有限群であろう. この主張は現在でも未解決である. 従って III(E/K)[2] が十分小さい（もっと言えば, 消えている＝ 自明な群となる）ときであれば, Sel2 (E/K) は E(K)/2E(K) に非常に近く, 計算出来たと言ってよ いことになる. 基本的に「楕円曲線の有理点の計算に失敗した」というケースは, そのほとんどが 「III(E/K)[2] が膨らんで精密に E(K)/2E(K) を計算出来なかった」という場合である. 以上から E(K)/2E(K) が計算出来たとしよう. 後はこれをヒントに E(K) を復元する作業が残さ れている. これを ∞-descent 法と呼ぶ. ここでは楕円曲線の有理点の複雑さをはかる高さ（height） という概念を導入して行われる. イメージとしては, E(K)/2E(K) から有理点の高さの上限を特定 し, それ以下の高さを持つ楕円曲線を虱潰しにあたり, 独立な有理点（生成元）をランクに達するま で捜索するという手法である. 13 発音は “シャア: sha” である. 実はこの記号は “「山」の縦棒が全部同じ長さ” の形が正しく, 下の横線が繋がっている. TEX ではこの記号を正確に出力出来ないので, I を 3 つ並べて書いている. 16 例 3.4. 実際に E(K) を計算してみよう. ここでは Sage にも導入されている Simon’s 2-descent パッ ケージを用いる. 但し Sage 版にはバグが存在している14 ため, 以下は Simon 自身による最新版の Pari/GP パッケージの結果15 を Sage の出力に合わせて書くことにする. √ √ 例として, K = Q( −7) 上の楕円曲線 E : y 2 = x3 + x + −7 に対して E(K) を計算してみる. Sage では sage: K.<a>=NumberField(x^2+7) sage: E=EllipticCurve(K,[0,0,0,1,a]) sage: E.simon_two_descent(verbose=1) と記述する（このケースではバグは影響せず, 修正版と同じ結果を返す）. a は二次拡大 K/Q の生 √ 成元で, この場合 a= −7 と思って良い. verbose はオプションで, 数字（0∼2）によって内部処理 をどの程度見せるかを調整する. この実行結果は以下のようになる. courbe elliptique : Y^2 = x^3 + Mod(1, y^2 + 7)*x + Mod(y, y^2 + 7) points triviaux sur la courbe = [[1, 1, 0], [Mod(1/2*y + 3/2, y^2 + 7), Mod(-y - 2, y^2 + 7), 1]] #S(E/K)[2] = 2 #E(K)/2E(K) #III(E/K)[2] rang(E/K) = 2 = 1 = 1 listpointsmwr = [[Mod(1/2*y + 3/2, y^2 + 7), Mod(-y - 2, y^2 + 7), 1]] (1, 1, [(1/2*a + 3/2 : -a - 2 : 1)]) 読み方を解説する（仏語に恐れる必要はない）. #S(E/K)[2] は Sel2 (E/K) のことであり, その位数 は 2 だと言っている. 更にその 2 つ下に #III(E/K)[2]（III(E/K)[2]）が消えている（自明な群であ る）というデータから, 結果として E(K)/2E(K) の位数は 2 であり, 更に torsion part が消えてい ることを確かめることで16 , E のランクは 1 であると主張している. また ∞-descent により, E(K) の自由部分の生成元を ( a+3 「ランクの 2 , −a − 2) と求めている. 最後の出力は順に「ランクの下界」 上界」 「見つかった E(K) の生成元」を表す. 即ち, この場合は計算が成功していることになる. なお E(K)tors = {0}（自明な群, つまり torsion part は無限遠点のみ）となる. √ 例 3.5. 別の例を考えよう. K = Q( 59) 上の楕円曲線 E : y 2 = x3 + 1728 に対し E(K) を同様に 計算してみると, 次のように出力される（途中経過は省略）. courbe elliptique : Y^2 = x^3 + Mod(y, y^2 - 59) ...omitted... #S(E/K)[2] = 4 #E(K)/2E(K) = 4 #III(E/K)[2] rang(E/K) = 1 = 1 [1, 2, [...points...]] 14 少し補足しておく. Sage に搭載されている Simon’s 2-descent パッケージは, 本来 Pari/GP で書かれたパッケージを 単に Sage に移植しただけである. 従ってソースコードも Pari/GP をベースに書かれている. 現在の最新版は Denis Simon のウェブページにて ell.gp というファイルで公開されている. 一方 Sage にも最新版を反映してもらうため, 開発者用のコ ミュニティページ developer-trac にて修正を依頼しているが, 未だ反映されていない. 15 最新版では, 出力が全て仏語から英語に変更されて読み易くなっている. 16 実行画面には表示されていないが, 有理点を探す過程で行われている. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 17 √ 283 points の部分には (−12, 0) と (− 133 59) が出力される. ここで最後の [1, 2] に注目であ 16 , − 64 る. E のランクの下界は 1 であるのに対し上界は 2 であるから, これではランクを特定出来ていない ように見えるが, その上に「ランクは 1 である」という表示がある. これはどういうことだろうか？ 実は, ランクの上界は単に Sel2 (E/K) の F2 -次元を表示しているだけである. 今 III(E/K)[2] が消 えているので E(K)/2E(K) ≃ Sel2 (E/K) が成り立つ. 更にランクは少なくとも 1 以上であること から, E(K) ≃ Z⊕2 or E(K) ≃ Z ⊕ E(K)tors with #(E(K)tors /2E(K)tors ) = 2 であることが分かる. しかし, 実際に (−12, 0) という位数 2 の元が見つかっているので, E(K) は自 明でない torsion part を持つことが分かる. よって E(K) ≃ Z ⊕ Z/2Z であり, 自由部分の生成元は √ 283 (− 133 59) と結論出来る. 16 , − 64 √ 例 3.6. E(K) を特定出来ない例も一つ挙げておこう. K = Q( 3 53) 上の楕円曲線 E : y 2 = x3 +1728 に対し E(K) を同様に計算してみると, 次のように出力される（途中経過は省略）. courbe elliptique : Y^2 = x^3 + Mod(y, y^3 - 53) ...omitted... #S(E/K)[2] #E(K)/2E(K) = 8 >= 2 #III(E/K)[2] <= 4 0 <= rang(E/K) <= 2 [0, 3, [...points...]] points の部分には, 位数 2 の元 (−12, 0) のみが表示されている. 更に III(E/K)[2] の位数は 4 以下 であることも分かっている. もし III(E/K)[2] = {0} であると仮定すると, 完全系列から E(K)/2E(K) の位数も 8 でなければ ならない（これが E(K)/2E(K) が最大となる場合である）. しかし既に位数 2 の元 (−12, 0) が見 つかっているので E(K) ≃ Z⊕3 はあり得ない. 従って E のランクは 2 以下であることが分かる. ま たこの位数 2 の元の存在から, E(K)/2E(K) の位数が 2 以上であることも分かる. しかしその他の 無限位数の有理点が全く見つかっていないので, ランクは特定出来ないということになる. このよう に III(E/K)[2] が非自明である可能性が出てきたときには, 計算が失敗に終わることが多い. 演習問題 3.7 (C, 8 点). Q でない代数体 K と, その上の楕円曲線を適当に 1 つずつ選び, ell.gp パッ ケージを用いて E(K) の計算を試みよ. Sage に含まれている（バグ込みの）関数を用いても構わな い. なお Pari/GP で計算を行う場合は, 以下のように実行すること（5.2 節も参照）. 1. gp calculator（gp.exe）と同じディレクトリに ell.gp をダウンロード. 拡張子は好きに付けて構わない （例えばテキストファイル ell.txt など）. 以降このファイルを ell.gp とする. Pari/GP 本体は http://pari.math.u-bordeaux.fr/index.ja.html から, ell.gp は以下から入手すること. http://www.math.unicaen.fr/~simon/ell.gp 2. gp calculator を起動し gp: \r ell.gp を実行. 続いて基礎体と楕円曲線を gp: bnf=bnfinit(f) gp: ell=ellinit([a1,a2,a3,a4,a6]) √ と入力する. 但し f は y を変数とする一変数多項式 で入力すること. 例えば K = Q( 43) ならば y^2-43 とする. 18 3. 最後に次を実行する. gp: bnfellrank(bnf,ell) 但しこのままでは途中の処理が表示されない. 表示させるにはコード序盤にある設定項目 “Affichage des calculs” の中の DEBUGLEVEL ell=0 を 1 に変更すればよい. 演習問題 3.8 (6 点). ある代数体 K と楕円曲線 E に対し E(K) を計算させた所, 以下の情報を得た. • Sel2 (E/K) の位数は 4, • III(E/K)[2] の位数は 2 以下, • 位数 2 の 互いに独立な 有理点が少なくとも 2 つ存在する. これらの情報から, E(K) の構造を特定せよ. 演習問題 3.9 (20 点). 旧バージョンの Sage には, 以下のような 2-descent に関するバグが存在した. このバグを解析しなさい. 即ち, 何が問題で計算が停止してしまうのかを論じなさい. sage: K = CyclotomicField(43).subfields(3)[0][0] sage: E = EllipticCurve(K, ’37’) sage: E.simon_two_descent() # long time (4s on sage.math, 2013) Traceback (most recent call last): ... RuntimeError: *** at top-level: ans=bnfellrank(K,[0,0,1, *** ^-------------------*** in function bnfellrank: ...eqtheta,rnfeq,bbnf];rang= *** bnfell2descent_gen(b *** ^-------------------*** in function bnfell2descent_gen: ...riv,r=nfsqrt(nf,norm(zc)) *** [1];if(DEBUGLEVEL_el *** ^-------------------*** array index (1) out of allowed range [none]. An error occurred while running Simon’s 2-descent program 注意：このバグは既に修正されたが, 工夫をしないと E(K) の生成元は全て求まらない. ＊＊＊ いよいよ最先端の話題に入る. 紹介したいものは山ほどあるが, 時間の関係上ここでは特に知られ ている次の 3 つの話題を概観する. 1. 合同数問題 2. バーチ・スウィンナートン-ダイヤー予想 3. 谷山-志村予想 まず最初の話題から始めよう. これは非常に昔から知られている整数論のトピックであり, 問題そ のものも簡単に理解出来る. 定義 3.10. n を自然数とする. 3 辺の長さが全て有理数となるような直角三角形で面積が丁度 n のも のが存在するとき, n は合同数（congruent number）であると言う. 例 3.11. 6 は合同数である. ピタゴラスの定理でおなじみの “3:4:5” の直角三角形を思い出そう. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 19 では, 何故このような素朴な問題に楕円曲線が関係してくるのだろうか？ — その答えは, 次の命題 の証明を見れば分かる. 命題 3.12. 1 は合同数ではない. 早速やってみよう. 背理法を使うことにして, 1 が合同数であると仮定する. すると a, b, c ∈ Q>0 で a2 + b2 = c2 かつ る. このとき α = c2 4 , 1 2 ab β= = 1 となるようなものが存在する17 . すぐに確かめられる通り a ̸= b であ (a2 −b2 )c 8 とおくと β 2 = α3 − α が成り立つ（実際に計算して確かめてみよ）. a, b, c ∈ Q>0 より α, β ∈ Q であり, 特に a ̸= b より β ̸= 0 である. これは, Q 上の楕円曲線 y 2 = x3 − x が有理点 (α, β)（α > 0, β ̸= 0）を持つことと同値である. しかし, 一方でこの楕円曲線の有理点を 全て求めてみると (0, 0), (1, 0), (−1, 0), O の 4 つしか無いことが計算によって確かめられる. 従ってこれは矛盾であり, 1 が合同数でないこと が示された. 実はより一般に次が成り立つ. 命題 3.13. n が合同数であるための必要十分条件は, Q 上の楕円曲線 y 2 = x 3 − n2 x のランクが 1 以上となる18 ことである. 更に n が合同数のとき, 3 辺の長さは楕円曲線上の有理点 (α, β)（β ̸= 0）を用いて a= α 2 − n2 2nα α 2 + n2 , b= , c= β β β と書ける. n = 1 の場合 y 2 = x3 − x のランクが 0 なので, 合同数でないことが分かる. 演習問題 3.14 (C, 8 点). 合同数となるような n を一つ挙げ, 直角三角形の 3 辺 a, b, c を求めよ. 但 し a, b, c が 全て整数でない有理数 となるようなものを探すこと. 演習問題 3.15 (C, 5 点). 157 は合同数である. 直角を挟む 2 辺 a, b は 6803298487826435051217540 411340519227716149383203 , 21666555693714761309610 411340519227716149383203 である. c を求めよ. このように 3 辺の長さが非常に複雑な有理数となることもしばしばある. このように, 各 n が与えられるたびに楕円曲線のモーデル・ヴェイユ群を計算する戦略は余り実用 的ではない（実際, n が大きくなるとうまくいかない）. そこでもっと簡単な判定規準が欲しくなる. 現時点では未解決だが, 正しいと考えられている次の予想を挙げておく. この予想が正しければ, n が 大きくなってもコンピュータを用いて比較的容易に判定が出来るようになる. 17 実際には, 三角形がつぶれないように a, b, c に更に条件が付くが, ここでは（どのみちそのような三角形は存在しないの で）気にしなくて良い. 18 つまり, 有理点が無限個存在するということ. 20 予想 3.16. n を平方因子を持たない自然数とする. 更に以下の集合を考える. An Bn Cn Dn { = # (x, y, z) : { = # (x, y, z) : { = # (x, y, z) : { = # (x, y, z) : } x, y, z ∈ Z | n = 2x2 + y 2 + 32z 2 } x, y, z ∈ Z | n = 2x2 + y 2 + 8z 2 } x, y, z ∈ Z | n = 8x2 + 2y 2 + 64z 2 } x, y, z ∈ Z | n = 8x2 + 2y 2 + 16z 2 このとき次は同値である. A. n は合同数である. B. n が奇数のとき 2An = Bn . n が偶数のとき 2Cn = Dn . この予想の大部分を解決したのが, 次の Tunnell の定理である. 定理 3.17 (Tunnell, 1983). 予想 3.16 において「A ならば B」が成り立つ. 更に BSD 弱 予想 を仮 定すれば「B ならば A」も成り立つ. 演習問題 3.18 (C, 但し手計算でも可, 8 点). 2014 が合同数であるか否かを判定し, 予想 3.16 を満た しているか考察せよ. さて, 定理 3.17 で登場した BSD 予想について述べよう. 本節の最初に紹介した通り, 楕円曲線の 階数を正確に決定することは非常に難しい. 従って, 何か「計算し易い対象」と関連付けることが重 要となる. この方面での非常に有名な予想として バーチ・スウィンナートン-ダイヤー予想（Birch and Swinnerton-Dyer conjecture）が挙げられる. 2 人の数学者 Birch と Swinnerton-Dyer の名前か ら付けられ, 略して BSD 予想とも呼ばれている. これはクレイ研究所によるミレニアム懸賞金問題 の一つであり, 証明に成功した者には 100 万ドルの報奨金が支払われることが約束されている. 予想 3.19 (BSD 弱 予想). E を Q 上の楕円曲線とし, L(s, E) を E の Hasse-Weil L 関数とする. このとき L(s, E) は C 上解析接続され, 更に次が成り立つ： （L(s, E) の s = 1 における零点の位数） ＝ （E のランク r） Hasse-Weil L 関数の定義はこの後すぐに述べるが, 先に重要な定理を一つだけ. 定理 3.20 (Kolyvagin, Gross-Zagier). r ≤ 1 のとき BSD 弱予想は正しい. では Hasse-Weil L 関数を定義しよう. まず { } E(Fp ) := (x, y) : x, y ∈ Fp | y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ∪ {O} と定義する. つまり E(Fp ) とは (y 2 + a1 xy + a3 y) − (x3 + a2 x2 + a4 x + a6 ) が p で丁度割り切れる ような整数の組 (x, y) に無限遠点 O を一つ付け加えたもの, 即ち E の p における還元 Ep の有理点 の集合である. この E(Fp ) を用いて ap (E) := p + 1 − #E(Fp ) を考える. 定義 3.21. L(s, E) := ∏ p∤∆(E) を E の Hasse-Weil L 関数と呼ぶ. ∏ 1 1 · −s 1−2s 1 − ap (E)p + p 1 − ap (E)p−s p|∆(E) 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 21 ここで最も重要なのは L(s, E) の s = 1 での零点の位数の計算の難しさ ＜ E のランクの計算の難しさ ということである. BSD 弱予想が正しければ E のランクを解析的情報から正確に特定出来るという 点が極めて重要なのである. 現時点ではこの予想は未解決であるが, この解析的情報には名前が付け られている. 定義 3.22. L(s, E) の s = 1 での零点の位数を, E の解析的ランク（analytic rank）と呼ぶ. Sage には, 解析的ランクを計算するコマンドがある： sage: E.analytic_rank() さて, 上の BSD 弱予想に対してもう少し精密な予想も考えられている. この予想に出てくる幾つ かの量は定義が複雑なので, 名前だけ述べておく. 予想 3.23 (BSD 強 予想). E を Q 上の楕円曲線とし, L(s, E) を E の Hasse-Weil L 関数とする. L(s, E) の s = 1 における Taylor 展開が L(s, E) = cran (s − 1)ran + · · · と書けているとする. このとき E のランクは ran に一致し, 更に ∏ ΩE · Reg(E) · #III(E/Q) · p cp cran = #E(Q)2tors が成り立つ. ここに ΩE は E の Archimedean period, Reg(E) は E のレギュレータ（regulator）, cp は玉河数（Tamagawa number）である. BSD 強予想は, テイト-シャファレヴィッチ群 III(E/Q) の有限性予想（予想 3.3 の K = Q の場合） にも言及していることに注意されたい. さて, BSD 予想において重要な量 ap (E) についてもう少し考察してみよう. まず ap (E) の大小に ついては次の Hasse の定理が知られている. 定理 3.24 (Hasse, 1933). p ∤ ∆(E) ならば次が成り立つ19 . √ √ −2 p ≤ ap (E) ≤ 2 p ここで唐突であるが, 次のような（複素）解析的関数を導入する. 今回は詳細を説明する余裕がな いので, ざっくりとした定義を述べる20 . 定義 3.25. 上半平面 h = {z ∈ C | Im(z) > 0} 上の正則関数 f : h → C で, 一次分数変換 ( ( ) ) a b az + b z ∈ h, γ = ∈ SL2 (Z), c ≡ 0 (mod N ) γ : z 7→ cz + d c d に対して f (γ(z)) = ε(d)(cz + d)k f (z) (k ∈ Z≥2 ) を満たすものを Q 上重さ k の保型形式（modular form）と呼ぶ. 更に N を f のレベル（level）, ε : (Z/N Z)× → C× を指標（character, 特別な場合は nebentypus）と呼ぶ. √ √ Mordell-Weil 群に書き換えると p + 1 − 2 p ≤ #E(Fp ) ≤ p + 1 + 2 p となる. つまり #E(Fp ) の上 界・下界評価となる. 逆にこの範囲の自然数 n を一つとったとき, #E(Fp ) = n となるような E が必ず構成出来ることも知 られている（Deuring の定理）. 20 いずれこの原稿に対応させて「計算する立場からの保型形式論入門」という原稿を書くつもりです. 19 この関係式は 22 補足 3.26. 厳密には, その性質に応じて「モジュラー形式」「保型形式」と言葉を使い分ける. この 場合, 前者を modular form, 後者を automorphic form と呼ぶ. 保型形式 f (z) は, 変数変換 q = e2πiz によって定義域を穴あき単位円盤に写すことが出来る. そこ で q による Fourier 展開 f (q) = ∑ an (f )q n (q = e2πiz ) n≥0 を考える. 実は ap (E) と ap (f ) が非常に強い絆で結ばれているはずだ, というのが, 最後のトピック 谷山-志村予想 である. 予想 3.27 (谷山-志村予想). Q 上の楕円曲線 E は modular である. 即ち, 導手 N の楕円曲線 E に 対し, 重さ 2（かつレベル N ）の保型形式 f が存在し, “ほとんど全ての素数 p に対して” ap (E) = ap (f ) が成り立つ. 但し “ほとんど全ての素数” とは 導手 N を割らない素数 という意味である. 補足 3.28. 実は, BSD 弱予想（予想 3.19）における「L(s, E) は C 上解析接続される」の部分は, 上 の予想が正しければ従う. 谷山-志村予想は, その特別な場合（E が半安定還元を持つ場合）が 1995 年に Wiles によって示さ れ, これを用いて Fermat の最終定理（n ≥ 3 のとき xn + y n = z n を満たす 0 でない自然数 x, y, z は存在しない, という定理）が証明された. その後, 最先端の理論を駆使して 2001 年に完全解決を 見た. 定理 3.29 (Breuil-Conrad-Diamond-Taylor, 2001). 谷山-志村予想は正しい. 例 3.30. 楕円曲線 E : y 2 = x3 − x は, 重さ 2, レベル 32 の保型形式 f (q) = q − 2q 5 − 3q 9 + 6q 13 + 2q 17 − q 25 − 10q 29 + · · · と対応している. 例えば p = 17 のとき #E(F17 ) = 16 となるので a17 (E) = 17 + 1 − 16 = 2 となり, 確かに a17 (f ) に一致していることが分かる. これらは sage: E=EllipticCurve([0,0,0,-1,0]) sage: E17=EllipticCurve(GF(17),[-1,0]) sage: E.ap(17) sage: E17.cardinality() sage: E17.points() とすれば良い. 演習問題 3.31 (C, 8 点). Q 上の楕円曲線 E : y 2 + y = x3 − x2 は, 保型形式 f (q) = q ∏ (1 − q n )2 (1 − q 11n )2 n≥1 と対応している（即ち, 谷山-志村予想が成立している）ことを, 導手を割らない 100 以下の素数 p に 対して確かめよ. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 23 この節の最後として, 紹介した内容よりやや進んだ内容について演習問題を残しておく. Q 上の楕 円曲線とその周辺の理論を学んだ後に, すぐに新しい研究に入るのは非常に難しい. 何故ならば Q 上 の理論はもうほとんど研究し尽くされており, 非常に難しい問題（例えば BSD 予想など）しか残っ ていない. 以下の話題は, 主に修士論文をこれから書こうとする学生さんに, 予め知っていて欲しい 知識を挙げたものである. 演習問題 3.32 (20 点). 楕円曲線は, アーベル多様体（abelian variery21 ）と呼ばれる代数的構造物 の特別な場合（次元が 1 の場合）である. このアーベル多様体について具体例と共に説明せよ. 演習問題 3.33 (20 点). ap (f ) としては通常 固有形式（eigenform）の Fourier 係数を考える. 1. Hecke 作用素（Hecke operator）の定義を述べなさい. 2. モジュラー形式 f が固有形式であることの定義を述べなさい. 演習問題 3.34 (20 点). 保型形式は各種一般化が存在し, それに応じて谷山-志村予想の一般化も盛ん に研究されている. 以下の一般化された保型形式から一つ以上選んで, それについて説明せよ. 具体 的な例も含めること. • ヒルベルト保型形式（Hilbert modular forms） • ジーゲル保型形式（Siegel modular forms） • ビアンキ保型形式（Bianchi modular forms） 演習問題 3.35 (20 点). 谷山-志村予想をより一般化したものとしてラングランズ対応（Langlands correspondence）に関する予想が挙げられる. これについて説明せよ（具体例は不要）. 演習問題 3.36 (30 点). BSD 強予想については, 本稿では詳細な説明は省いた. これについて正確な 解説を付けなさい. 即ち • Ω(E)：E の Archimedean period • Reg(E)：E のレギュレータ（regulator） • cp ：玉河数（Tamagawa number） について正確な定義を与えなさい. 演習問題 3.37 (30 点). 補足 3.28 を証明せよ. 即ち, 谷山-志村予想を仮定することで何故 L(s, E) が C 上解析接続可能となるのかについて論じよ. 演習問題 3.38 (40 点). 最近 BSD 予想の p 進版（p-adic version）の定式化が行われている. これに ついて, 以下の順序で論じよ. 1. p 進数体 Qp の定義を述べよ. 2. p 進 L 関数とはどういうものか述べよ. 3. 以上を基に, p 進版 BSD 予想について述べよ. 4. p 進版 BSD 予想を満たすような具体例を一つ挙げよ. 21 幾何学での多様体は manifold と英訳されている. これとは異なることに注意. 24 次の 2 つの演習問題は, 2 節及び 3 節で学んだ内容の総復習となっています. レポート問題として おすすめです. なお 3.39 が理論で解きたい人向け, 3.40 が計算機で解きたい人向け です. 演習問題 3.39 (5. のみ計算機利用可, 20 点). 次の主張に対し, その真偽を判定せよ. 各々について 簡単な理由（証明・反例等）をつけること. なお, 以下では全て E は Q 上の楕円曲線とする. 1. 2 つの楕円曲線 E1 , E2 に対し N (E1 ) ̸= N (E2 ) ならば, E1 と E2 は同型でない. 2. E 上の点の集合 E(R) := {(x, y) ∈ E : x, y ∈ R} ∪ {O} を考える. このとき E(R) は有限生成 アーベル群である. 3. #III(E/Q)[2] = 1, #Sel2 (E/Q) = 16 ならば E のランクは 4 である. 4. Q 上至る所 悪い 還元を持つような楕円曲線は存在しない. 5. E : y 2 = x3 + x + 2 に対して p1 < p2 （素数）ならば #E(Fp1 ) < #E(Fp2 ) が成り立つ. なお N (E) = 56 = 23 · 7 より p1 , p2 ̸= 2, 7 とせよ. 演習問題 3.40 (C, 20 点). 以下の 1 後の 問題 A∼C に答えなさい. なお ∼ 13 15 に最も良くあてはまる数字・記号を入れ, その には「ある」「ない」の何れかが入る. Q 上の楕円曲線 E1 : y 2 + y = x3 + x2 − 8x + 19 を考える. このとき b2 = 1 , b4 = であり, 更に ∆(E1 ) = 7 2 , b6 = , N (E1 ) = 3 8 , b8 = 4 , c4 = 5 , c6 = である. 従って E1 は BE1 = { 9 6 , 10 } の外 で至る所良い還元を持つ. 次に別の Q 上の楕円曲線 E2 : y 2 = x3 − 49x を考える. このとき E2 のランクの下限は であり E2 (Q)tors ≃ 位数は 14 12 である. 従って 7 は合同数で なので, E2 のランクは 15 13 11 . またこのとき E2 (Q)/2E2 (Q) の と確定できる. 問題 A E1 及び E2 のグラフを描きなさい. 問題 B E1 及び E2 を p = 23 で還元する. #E1 (F23 ), #E2 (F23 ) を求めなさい. 問題 C E1 と E2 は同型か, 理由もつけて答えなさい. Sage には他にも様々なドキュメントが用意されている. そのほとんどは英語で書かれているが, 頑張って読んでみることをお薦めするa . Sage に関する全般的な情報, また各種 OS 用バイナリ （Sage 本体）のダウンロードについては http://www.sagemath.org/ を参照のこと. また Reference Manual は http://www.sagemath.org/doc/reference/ からアクセス出来る. a 横山も現在, Sage に関する日本語の纏まった解説を書きたいと考えています（本稿もその一環）. 協力して下さる 方も絶賛募集中です. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 25 楕円曲線暗号入門 4 最後の話題として, 産業数学への一つの応用である楕円曲線暗号の初歩を概観する. 内容としては, この資料の最後に挙げた参考文献の 6. を参照した. 本節を通じて有限体上かつ簡易版の楕円曲線 E = E ′ : y 2 = x3 + ax + b を扱う. その代わり基礎体は Fp だけではなく, その有限次拡大 Fq （q = pm ：p 冪）も考える. どち らの場合もその標数は p である. まずは等分点と呼ばれる概念を定義する. 以下, 特に断りが無けれ ば定義体は Fp または Fq の何れかとする. 定義 4.1. P ∈ E であって mP = O（m 倍すると無限遠点・ ・ ・群演算の単位元） となるようなものを E の m 等分点（m-division point）と呼び, その全体を E[m] と書く. 命題 4.2. m が p と互いに素とする. 今 E の定義体を Fq まで拡大したとき, E の m 等分点全体は E[m] ≃ Z/mZ ⊕ Z/mZ となる. p|m の場合については m = pr m′ （p ∤ m′ ）として E[m] ≃ Z/m′ Z ⊕ Z/m′ Z or Z/mZ ⊕ Z/m′ Z が成り立つ. 以上より E/Fq の m 等分点は高々 m2 個であることが分かる. ここでモーデル・ヴェイユ群の構造がどうなっているか考えてみる. 基礎体が Q の場合は有限生成 アーベル群であったが, 基礎体が有限体の場合はそもそも有理点が有限個である. より正確に次が成 り立つ. 定理 4.3. Fq 上の楕円曲線のモーデル・ヴェイユ群 E(Fq ) の構造は, 巡回群または E(Fq ) ≃ Z/m1 Z ⊕ Z/m2 Z (m1 | m2 , m1 | q − 1) となる. E(Fq ) が高々2 個の巡回群の組み合わせにしかならないことを示しておこう. E(Fq ) は有限群である から E(Fq ) ≃ r ⊕ Z/mi Z (mj | mj+1 ) i=1 mr1 個存在する. しかし命題 4.2 より r ≤ 2 が従う. ここで楕円曲線暗号において有名なクラスの一つである超特異楕円曲線を定義する. この特別な曲 線を扱った場合, 楕円曲線暗号（正確には後に述べる離散対数問題）が比較的容易に解けてしまうこ と書ける. これにより E の m1 等分点は とが幾つかの場合に知られている. 定義 4.4. E を Fq 上の楕円曲線とする. q + 1 − #E(Fq ) ≡ 0（mod p）となるような E を超特異 （supersingular）楕円曲線と呼ぶ. 例 4.5. F5 上の楕円曲線 E : y 2 = x3 + 1 は超特異楕円曲線である. 何故ならば E(F5 ) = {(0, 1), (0, 4), (2, 2), (2, 3), (4, 0), O} より #E(F5 ) = 6 となるからである. 演習問題 4.6 (C, 但し手計算でも可, 5 点). F7 上の楕円曲線 E : y 2 = x3 + x は超特異楕円曲線で あることを示せ. 26 ではいよいよ楕円曲線暗号の詳細に入る. 楕円曲線暗号を解くとは, 楕円曲線に関する離散対数問 題を解くことを意味する. まずはこの離散対数問題を定義する. 定義 4.7. E を Fp 上の楕円曲線とし. 点 P ∈ E をとる. 更に整数倍点 Q = dP （0 ≤ d < ord(P )） が与えられているとする. ここで ord(P ) は P の位数とする. この P, Q という 2 つの情報のみから d を特定する問題を 楕円曲線離散対数問題（Elliptic Curve Discrete Logarithm Problem）と呼び, 略して ECDLP と称する. 例 4.8. F7 上の楕円曲線 E : y 2 = x3 + 2x + 3 上の点 P = (3, 6) と Q = dP = (3, 7) が与えられて いるとき, d を求めると d = 14 となる. これは 2P, 3P, · · · と総当たりで求めても P の位数が 18 な ので簡単に求まる. 例 4.9. 基礎体の標数を増やしてみる. F1010 +19 上の楕円曲線 E : y 2 = x3 + 2x + 3 上の点 P = (3, 6) と Q = dP = (975723440, 3514777868) が与えられているとき, d を求めると d = 2392892251 であ る. 実は P の位数は 2499996514 であり, これは先の例のようにすぐには求まらない. 演習問題 4.10 (C, 6 点). F103 上の楕円曲線 E : y 2 = x3 + 2x + 3 上の点 P = (2, 85) とその整数 倍点 Q = dP = (11, 29) が与えられているとき, d を求めよ. 上の 2 つの例から分かる通り, 楕円曲線上の点の位数が巨大な場合は d を特定することが極端に難し くなる. 実際, 現在知られている d の特定アルゴリズムは全て, 点位数の多項式時間またはそれ以上 となっている. この現象は丁度, 素因数分解が桁数の増加によって極端に困難となることに良く似て いる. 楕円曲線暗号はある意味で「素因数分解の “楕円曲線版” が難しい」ことを利用した方式と言 える. 折角なので, 素因数分解の困難性に安全性を委ねている公開鍵暗号方式22 の一つである RSA 暗号 （RSA cryptosystem）を紹介しておこう. この名前は 3 人の開発者 Rivest-Shamir-Adleman のイニ シャルを冠したものである. アルゴリズム 4.11. 平文 M を暗号化して送信し, 復号化することを考える. 1. 2 つの大きめの素数 p, q を選び n = pq を計算する. 2. gcd(e, φ(n)) = 1 を満たすような e ∈ N を一つとる. 但し φ(n) は Euler 関数で, n 以下の自然 数のうち n と互いに素なものの個数を表す. 今の場合 φ(n) = (p − 1)(q − 1) である. 3. de ≡ 1（mod φ(n)）を満たすような d ∈ Z を求める. 以上の手順により, 公開鍵 (n, e) 及び秘密鍵 (p, q, d) を得る. これを用いて次のように通信を行う. • 0 でない整数 M を c ≡ M e （mod n）と暗号化し, 送信する. • 受信した c を M ≡ cd （mod n）で復号化する. 但し, 合成数 n は M < n を満たすように選んでおかなければならない. 従って平文が長くなればよ り巨大な素数 p, q が必要となる. なお本稿では次ページの ASCII コードを相互変換に用いる. 22 普通の錠前のように, 閉めるための鍵と開けるための鍵が同一の方式を秘密鍵暗号方式と呼ぶのに対し, これは閉めるた めの鍵と開けるための鍵が異なる. 従って暗号化のための（＝閉めるための）鍵を公開出来るようになっており, 鍵の受け渡 しに生じるリスクを回避出来るようになっている. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 27 +----------------------------------------------------+ | A B C D E F G H I J K L M | | 65 66 67 68 69 70 71 72 73 74 75 76 77 | +----------------------------------------------------+ | N O P Q R S T U V W X Y Z | | 78 79 80 81 82 83 84 85 86 87 88 89 90 | +----------------------------------------------------+ それでは Sage を使って, 平文 HELLOWORLD を RSA 暗号方式で暗号化・復号化してみよう. まず この平文を M に変換して M = 72697676798779827668 を得る. そして 2 つの素数を用意する. sage: p = (2^31) - 1; p 2147483647 sage: is_prime(p) True sage: q = (2^61) - 1; q 2305843009213693951 sage: is_prime(q) True sage: n = p*q ; n 4951760154835678088235319297 次に e を求める. sage: e = ZZ.random_element(euler_phi(n)) sage: while gcd(e, euler_phi(n)) != 1: ... e = ZZ.random_element(euler_phi(n)) ... sage: e # random 1850567623300615966303954877 sage: e < n True Python ベースのプログラミングにおいては, for ループなどの処理はインデント（字下げ：indent） で行う. 2 回 Enter を行い空白の行を作ることでループを抜ける命令を実行出来る. 次に d を求める. sage: bezout = xgcd(e, euler_phi(n)); bezout (1, 4460824882019967172592779313, -1667095708515377925087033035) sage: d = Integer(mod(bezout[1], euler_phi(n))) ; d 4460824882019967172592779313 sage: mod(d*e, euler_phi(n)) 1 以上により公開鍵は (n, e) 及び秘密鍵は (p, q, d) が出揃い, それぞれ • n = 4951760154835678088235319297 • e = 1850567623300615966303954877 • p = 2147483647 28 • q = 2305843009213693951 • d = 4460824882019967172592779313 と求まる. これを用いて暗号化を行う. sage: mod(m^e, n) ---------------------------------------------------RuntimeError Traceback (most recent call last) /home/mvngu/<ipython console> in <module>() /home/mvngu/usr/bin/sage-3.1.4/local/lib/python2.5/ site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__pow__ (sage/rings/integer.c:9650)() RuntimeError: exponent must be at most 2147483647 実行してみると, オーバーフローを起こして強制終了してしまう. これは扱う値の桁数に限度がある ためで, このような場合は次のように逐次 mod 計算を行うことで桁数を抑える工夫を行う. sage: c = power_mod(m, e, n); c 630913632577520058415521090 このビルトイン関数 power mod は簡単に自作出来る23 ： def power_mod(a, b, n): d = 1 for i in list(Integer.binary(b)): d = mod(d * d, n) if Integer(i) == 1: d = mod(d * a, n) return Integer(d) この c を送信し, 受信者は最後に復号化を行う. sage: power_mod(c, d, n) 72697676798779827668 sage: m 72697676798779827668 きちんと最初の平文 HELLOWORLD が復号化されているのが確認出来る. +----------------------------------------+ | H E L L O W O R L D | | 72 69 76 76 79 87 79 82 76 68 | +----------------------------------------+ 演習問題 4.12 (C, 15 点). 自分の名前（例えば著者の場合は SHUNICHIYOKOYAMA）を RSA 暗号方 式で暗号化・復号化しなさい. 補足 4.13. 少し誤解され易いが「100 桁の合成数を素因数分解することの難しさ」と「100 桁の数が 素数であるかを判定することの難しさ」は全く異なる. 一般に前者の方が後者よりも難しく, このよ うな暗号に用いられる大きな素数も比較的容易に生成出来る. 23 SageMath Cloud ではエラーが出るが, 原因は不明で現在特定中である. 旧バージョンの Sage（ver.5 系列）ではエラー は出ない. 29 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 補足 4.14. 楕円曲線上の点 P , Q = dP から d を特定する問題をどうして離散 対数 問題と呼ぶのか について補足する. 実はこの操作は上述した RSA 暗号方式における冪剰余算に対応している. 違い はその演算が加法的か乗法的かの違いだけである. このとき何らかの数を法とした世界で P d = Q と なり, P, Q から d を求める問題と見なすことが出来る. この式を書き換えると d = logP Q となるこ とが「対数問題」の名の由来である. P, Q ∈ R ならば d を求めることは非常に易しい（高校数学で 学んだように, 連続かつ単調変化する）が, P, Q が離散的に変動する場合は logP Q も離散的に（不 規則に）変化するため, 特徴を追う（解読する）ことが非常に難しくなるのである. さて, ここで「楕円曲線暗号」という言葉に明確な定義を与えておこう. 楕円曲線暗号の安全性は, 楕円曲線離散対数問題の難しさとほぼ同義である. 定義 4.15. 楕円曲線離散対数問題（ECDLP）の困難性に安全性の根拠を置いた公開鍵暗号のこと を 楕円曲線暗号（Elliptic Curve Cryptography：ECC）と呼ぶ. 楕円曲線暗号が RSA 暗号に比べて優れている点の一つとして, 鍵長を小さく出来ることが挙げられ る. 2 進数展開したときの桁数の単位をビット（bit）と呼ぶ. 例えば 9 = 23 + 20 = 10012 は 4 ビッ ∑1023 トである. RSA 暗号を十分安全に利用するために必要な鍵長はおよそ 1024 ビット（ k=0 ak 2k , ak = 0, 1 程度の膨大な数）となるが, 楕円曲線暗号の場合はおよそ 160 ビット程度で十分な安全性 が確保出来ることが知られている. 従って楕円曲線暗号はハードウェアの資源を節約したい場合や, モバイル端末など小型機器において実装がし易く有用である. 演習問題 4.16 (C, 15 点 / cf. 参考文献 6. の例 2.5). n ビット長の鍵を利用した RSA 暗号を攻撃する ために最も有効な（良く用いられる）方法として 数体篩法（number field sieving method）が挙げられ 1/3 る. これは大きな素数の素因数分解アルゴリズムとなっており, その計算量は T1 (n) = C1 en (log n)2/3 （C1 は定数）であることが知られている. 一方, m ビット長の鍵を利用した楕円曲線暗号を攻撃する ために最も有効な（良く用いられる）方法として ρ 法（rho method）が知られており, その計算量は T2 (m) = C2 2m/2 （C2 は定数）であることが知られている. 攻撃者の攻撃能力の限界を T と置けば T = T1 (n) = CT2 (m) （C は定数） となり, T よりも大きく（但し大きくなり過ぎないように）n, m を調整すれば安全な暗号を利用出来 る. 上で述べた「1024 ビット RSA 鍵＝ 160 ビット ECC 鍵」は T1 (1024) = CT2 (160) という関係式を意味する. 以上を参考にして, 4096 ビット RSA 鍵と同等の安全性を持つ ECC 鍵の ビット数を求めなさい. 演習問題 4.17 (6 点). 上の演習問題 4.16 において, 対数の底（> 0, ̸= 1）が指定されていないが, 計 算量を評価する場合は（計算し易いように）好きな底を選んで良く, これによって計算量が変わるこ とは無い. それは何故か説明しなさい. 一方で, 秘密鍵暗号においても楕円曲線を活用することが出来る. 秘密鍵を直接相手に送ることな く「送信者と受信者が同じ鍵を共有出来る」手法の一つにディフィー・ヘルマン鍵共有が挙げられる. アルゴリズム 4.18. 大きな素数 p を一つ生成しておき, 乗法群 (Z/pZ)× の生成元 g を予め計算し ておく. この p, g は公開・共有する. A,B の二者間で通信を行うことを想定し, お互いそれぞれ乱数 （但し 0 以上 p − 2 以下で, なるべく大きなもの）を生成して保持しておく. これをそれぞれ rA , rB とおく. 30 1. A は XA ≡ g rA （mod p）を計算し, B に送信する. 2. B は XB ≡ g rB （mod p）を計算し, A に送信する. rA 3. A は B からの計算結果を用いて KA ≡ XB （mod p）を計算する. rB 4. B は A からの計算結果を用いて KB ≡ XA （mod p）を計算する. このとき KA = KB ≡ g rA rB となるので, これを両者の秘密鍵として利用することが出来る. この手 法を ディフィー・ヘルマン鍵共有（Diffie-Hellman key exchange）と呼ぶ. この方式は XA , XB が 通信中に盗まれても KA （= KB ）を特定することが極めて難しい点に安全性の根拠を置いている. この鍵共有方式の楕円曲線版は, 冪剰余算を Fp 上の楕円曲線における点の足し算に対応させて作る ことが出来る. アルゴリズム 4.19. 大きな素数 p を一つ生成しておき, Fp 上の楕円曲線 E, 及び E 上の点 P を予め 用意しておく. この E, P は公開・共有する. A,B の二者間で通信を行うことを想定し, お互いそれぞ れ乱数（但し 0 以上 ord(P ) − 1 以下で, なるべく大きなもの）を生成して保持しておく. これをそれ ぞれ rA , rB とおく. 1. A は XA = rA P を計算し, B に送信する. 2. B は XB = rB P を計算し, A に送信する. 3. A は B からの計算結果を用いて KA = rA XB を計算する. 4. B は A からの計算結果を用いて KB = rB XA を計算する. このとき KA = KB = rA rB P となるので, これを両者の秘密鍵として利用することが出来る. この 手法を 楕円曲線ディフィー・ヘルマン鍵共有（Elliptic Curve Diffie-Hellman key exchange）と呼 び, 略して ECDH 鍵共有と呼ぶ. この方式は XA , XB が通信中に盗まれても KA （= KB ）を特定 することが極めて難しい点に安全性の根拠を置いている. 演習問題 4.20 (C, 10 点). F100003 上の楕円曲線 E : y 2 = x3 + x + 6 と E 上の点 P = (2, 4) をと る. このとき ord(P ) = 33213 である. 上のアルゴリズム 4.19 に従って rA , rB （但しどちらも 10000 以上）をそれぞれ一つずつ選び, ECDH 鍵共有を試みよ. 即ち XA , XB , KA , KB を求めて KA = KB が成り立つことを確かめよ. 定義 4.21. XA , XB , P から KA （= KB ）を特定する問題を 楕円曲線ディフィー・ヘルマン問題 （Elliptic Curve Diffie-Hellman Problem：ECDHP）と呼ぶ. ECDHP は ECDLP よりも易しい問題である. 何故なら XA , P から rA を特定出来る（ECDLP が 解ける）ことを仮定すれば KA = rA XB も計算出来てしまうからである. 演習問題 4.22 (6 点). ECDHP が解けることを仮定しても ECDLP が解けるとは限らない. それは 何故か説明しなさい. ECDH 鍵共有方式のアイデアを用いて, 楕円曲線エルガマル暗号と呼ばれる 公開鍵暗号方式 を実 現することが出来る. アルゴリズム 4.23. 大きな素数 p を一つ生成しておき, Fp 上の楕円曲線 E, 及び E 上の点 P を予め 用意しておく. この E, P は公開・共有する. 送信者 A から受信者 B に対し平文 M ∈ E の送信を行 うことを想定する. 先程と同様, お互いそれぞれ乱数（但し 0 以上 ord(P ) − 1 以下で, なるべく大き なもの）を生成して保持しておく. これをそれぞれ rA , rB とおく. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 31 1. B は PB = rB P を計算する. rB は秘密鍵として保管し, PB は公開する. 2. A は R = rA P を計算し, 更に B による公開鍵を用いて XA = rA PB を計算する. これを用い て C = M + XA を計算し, (C, R) を B へ送信する. 3. B は受け取った (C, R) と保持していた rB を用いて XB = rB R を計算する. 最後に M ′ = C − XB を計算する. このとき M = M ′ となる24 ので, 平文の暗号化通信が成立する. この暗号を 楕円曲線エルガマル暗 号（Elliptic Curve ElGamal Encryption）と呼ぶ. 秘密鍵共有と大きく異なる点は, 通信に利用する情報（暗号文）が (C, R) に変わっていることであ るが, ここに重要な性質が隠されている. 秘密鍵共有においては XA , XB を双方向に通信していた が, これら同士を足したりしても何の意味もない. しかし楕円曲線エルガマル暗号における暗号文に ついては次が成り立つ. 命題 4.24. 平文 M ∈ E による暗号文を (C, R), 平文 M ′ ∈ E による暗号文を (C ′ , R′ ) とする. こ のとき, 平文 M + M ′ ∈ E による暗号文は (C + C ′ , R + R′ ) となる. 演習問題 4.25 (6 点). 上の命題 4.24 を示せ. 上の性質を加法に関する準同型性と呼ぶ. この性質は, 平文を知らなくても新しい暗号文を生成出来 てしまうことを意味する. しかしながら, 勿論暗号文を扱うことは出来ても平文を特定することは難 しいので, 安全であることには変わりない, 一方 RSA 暗号などは乗法に関する準同型性を持ってい ることになる. 実は, 加法に関する準同型性と乗法に関する準同型性を併せ持つ暗号方式が存在する. これによっ て, より自由に暗号文を扱うことが可能となる. 定義 4.26. 加法に関する準同型性と乗法に関する準同型性を併せ持つ暗号のことを 完全準同型暗号 （Fully-holomorphic Encryption）と呼ぶ. 完全準同型暗号の開発に初めて成功したのは IBM の Craig Gentry で, 2009 年のことである. 完全 準同型暗号の調査はまだまだ発展途上であり, 現在活発に研究が行われている. 演習問題 4.27 (20 点). 最近の完全準同型暗号の研究に関して調査し, 論じなさい. 演習問題 4.28 (20 点). 暗号化・復号化にあたっては, 悪意のある攻撃者からのなりすましを防ぐた め, 電子的な署名を付けられるような手法も幾つか確立されている. このような証明を デジタル署名 （digital signature）と呼ぶ. 楕円曲線を用いたデジタル署名として ECDSA 署名 と呼ばれるもの が知られている. これについて論じなさい. 演習問題 4.29 (20 点). ECDLP を解くための詳しい手法を述べる時間が無かったので, 演習問題と しておく. まず誰でも思いつきそうな戦略として 2P, 3P, 4P, · · · と虱潰しに計算して行き Q = dP と等しくなるまで続けるという戦略である. これを総当たり法／ ブルート・フォース法（brute force method）と呼ぶ. しかしこれでは時間がかかり過ぎてとても解 くことは出来ない. そこで良く知られている手法としては 24 各自で証明を試みよ. 授業中に解く時間をとる可能性もある. 32 • Baby-step Giant-step 法 • ρ法 の 2 つが挙げられる. 特に ρ 法は先程登場したが, 詳しく述べられなかった. この 2 つについて論じ なさい. 演習問題 4.30 (20 点). ρ 法は幾つかの高速化戦略が知られている. これについて論じなさい. 演習問題 4.31 (20 点). この節の前半に「超特異楕円曲線を用いた場合 ECDLP が比較的容易に解 けてしまう」と述べた. これは Menezes-岡本-Vanstone による結果である. これについて調査し, 論 じなさい. 演習問題 4.32 (20 点). ECDLP を解くための有用な道具として近年注目されているものの一つに ペアリング（pairing）がある. ペアリングは端的に言えば, Fq 上の楕円曲線の点に関する双線型写像 （bilinear map）のことである. 1. Fq 上の楕円曲線の 2 つの点から乗法群 G への写像 e : E(Fq ) × E(Fq ) → G がペアリングで あることの定義を述べなさい. 2. 逆にペアリングを用いて新しい暗号を構築する研究も進んでおり, 例として ID ベース暗号が 挙げられる. これについて調査し, 論じなさい. 演習問題 4.33 (20 点). 2009 年に Bos-Kaihara-Kleinjung-Lenstra-Montgomery によって, 112 ビット の ECDLP が解かれた. この結果自体も話題になったが, 特にこの成果が家庭用ゲーム機 PlayStation 3 を数百台用いて得られたことも有名である. この結果を含め, 最近の ECDLP へのチャレンジとそ の成果について調査し, 論じなさい25 . 25 Certicom 社という会社が, このチャレンジに対して懸賞金をかけている. この取り組みを総じて Certicom Challenge と呼ぶ. 33 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 数式処理システムを用いた計算実習 5 単位を申請する人は, 以下の演習問題を解いて, 実習時間内に提出すること. 演習問題（注：最終レポート問題ではありません） 以下の 1 ∼ 15 に最も良くあてはまる 数字・記号を入れ, その後の 問題 A∼G（Pari/GP を利用する場合は 問題 A∼D）に答えなさい. Q 上の楕円曲線 E : y 2 + xy = x3 + 12948x + 421776 を考える. このとき b2 = 1 であり ∆(E) = は BE = { 8 , b4 = , b6 = 3 , b8 = 4 , c4 = 5 , c6 = 6 である. 関数 factor(n) を利用して ∆(E) を素因数分解することにより, E 7 , 2 9 , 10 , 11 } の外で至る所良い還元を持つことが示される. しかも E は任意の p ∈ BE において乗法的還元を持つ ので, N (E) = 12 となる. 更に E(Q) ≃ 13 で, その生成元は P = 14 である. 最後に ap (E)（p は素数で p ≤ 20） を全て列挙すると { 15 } となる. 問題 A 下線部を N (E) を計算することなく 示しなさい. 問題 B #E(F11 ) を求めなさい. 問題 C Q = (4344, 284244) は無限位数の整数点であることを確認しなさい. 問題 D nP + Q が E の整数点でなくなるような最小の n ∈ N を求めなさい. 以下は SageMath Cloud を利用している場合のみ答えよ. 問題 E E について BSD 弱予想が成り立つことを確かめなさい, 問題 F E のグラフを描きなさい. 問題 G E を p = 11 で還元したもののグラフを描きなさい. 実習レポートの提出について SageMath Cloud で計算を行い, 以下の要領で作成すること. • 基本的に解答は全て, 所定の用紙に記入して提出すること. • 1 ∼ 15 は答えのみ解答せよ. • 問題 A∼G は実行プログラムとその実行結果を同封すること. 形式は SageMath Cloud のノートブックを印刷したもの で統一する. Sage のコマンドに関しては本稿でも幾つか紹介したが, 別途 Sage Quick Reference Card の日本 語訳版26 を配布するので, 参照しながら実習に取り組むこと. 特に Elementary Number Theory の項 が参考になると思われる. 26 日本語訳版は沼田泰英氏（信州大学）作成. 34 5.1 SageMath Cloud の利用法 Sage のコマンドに関しては, 本稿の 2,3 節及び配布した Reference Card を参照してもらうことに して, ここではクラウドサービス SageMath Cloud の利用法について解説する. 試験版（β 版）と して立ち上がった当初はサーバの不調やトラフィックの問題などから非常に使いにくいものとなって いたが, 最近ではかなり改善されており, 比較的快適に利用出来るようになった. ここからは https://cloud.sagemath.com/ にアクセスし, 順を追って利用法を見て行こう. なお, より詳細なドキュメントや開発途上のデータ 等は, 同じくクラウド開発環境 GitHub（ギットハブ）による https://github.com/sagemath/cloud/ を参照のこと. なお, 以下の手順及びキャプチャ画面は 2014 年 4 月 20 日 現在のものである. 多少 の変更は随時行われているので, 注意が必要である. 上が SageMath Cloud のログイン画面である. まずはアカウントの新規登録（勿論無料）から始め よう. 必要なのは氏名とメイルアドレス, そしてパスワードである. パスワードは自分で好きに設定 出来る27 . 上の画面の “create an account” をクリックして進むと, 入力画面に移る. 全てを入力したら, 最後に “I agree to the SageMathCloud Terms” のチェックボックスに忘れずに チェックを入れて, アカウント作成のボタンを押せば完了である. アカウントの作成が終わったら, いよいよログイン（ここではサインイン（sign in）と同義）する. アカウントが正常に発行されていれば, 次ページのようなトップ画面が表示されるはずである. この 画面で特に初期設定等は必要ない. 27 但しパスワードには「十分安全な」ものを選ぶこと. 余りにも短すぎたり, メイルアドレスと重複するワードなどの使用 は避けるべきである. 逆に難しくし過ぎて, 自分が忘れてしまわないように気を付ける必要もある. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 35 右上に登録したメイルアドレスが表示されているはずである. これがアカウント ID を兼ねる. 次に 左上の “Projects” から, 新規プロジェクトを作成する. 初めて SageMath Cloud を使う場合は, 何もリストが表示されていないはずなので “New Project” を選ぶ. この画面が出てきたら, プロジェクト名を入力する. “Description” は備考欄なので空欄で良い. “Create Project” をクリックすれば, 次の画面が表示される. 36 この “Create or Import a File, Worksheet, Terminal or Directory” をクリックする. ここではファイルの種類を選ぶことが出来る. 以前作成した Sage ワークシートもここからアップ ロードして利用することが出来る. また Sage ワークシートだけではなく LATEX ファイルの取り扱い も可能となっている. なお LATEX では Sage モードと呼ばれる機能が搭載されており, 例えば Sage での実行結果をそのまま LATEX の出力（pdf 等）に反映出来るようになっている. 例えば教育用途で は, 自動で解答を作成する（問題文を変えても, 再コンパイルすれば自動で更新される）などの活用 法がある. 但し, 日本語での出力は（恐らく）対応していないと思われるので注意すること. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 37 さて, ひとまず今回は Sage ワークシートを作成する. 後は普通に Sage をノートブック形式で利用 出来る. 実行は Shift+Enter で行うことが出来る. ヘルプやその他サポートに関する情報は, 左上の “Help” から参照出来る. また設定のページ “Project Control” では, 利用しているサーバの稼働状況などのテクニカルな情報 を確認出来る. 38 更に進んで, SageMath Cloud の開発・運営に参加したいという場合, または現在どのように開発が 進められているのかを知りたい場合は, 最初に紹介した GitHub のページをご覧頂きたい. Sage に 関する他のパッケージ開発についても GitHub への移行がほぼ完了している. 5.2 Pari/GP の利用法 Sage が扱えない環境（特に Windows OS）を想定して, 数式処理システム Pari/GP を用いて計算 を行う. 本体は Pari/GP のウェブページ（日本版） http://pari.math.u-bordeaux.fr/index.ja.html から入手出来る. 以下 Q 上の楕円曲線のみを考える. まず楕円曲線を定義する. gp: E=ellinit([1,2,3,4,5]) とすれば E は楕円曲線 y 2 + xy + 3y = x3 + 2x2 + 4x + 5 となる. さて, 出力結果に [1, 2, 3, 4, 5, 9, 11, 29, 35, -183, -3429, -10351, 6128487/10351, [... と数字が列挙されているはずである. これらは順に ai （i = 1, 2, 3, 4, 6）, bi （i = 2, 4, 6, 8）, ci （i = 4, 6）, ∆(E), j(E) を表す. 一つだけを取り出したければ, 例えば gp: E.disc とすれば良い. 他も同様に E.a2, E.j 等と書く. 次に E のモーデル・ヴェイユ群の torsion part E(Q)tors を求めてみる28 . gp: elltors(E) とすれば, 群の情報が読み取れる. この場合は自明な群となるはずである. Pari/GP の群の出力は少 し特殊なので, 読み方に気を付けること. 例えば演習問題 2.31 で扱った楕円曲線 y 2 = x3 − 43x + 166 の場合は 28 E(Q) の free part を計算するためには, 追加パッケージ elldata が必要である. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 39 gp: E=ellinit([0,0,0,-43,166]) gp: elltors(E) [7, [7], [[3, 8]]] と出力される. この出力は, 位数 7 の巡回群 C7 ≃ Z/7Z を表す. 別の楕円曲線 y 2 + xy = x3 − 1070x + 7812 で試してみると gp: E=ellinit([1,0,0,-1070,7812]) gp: elltors(E) [16, [8, 2], [[34, 88], [-36, 18]]] となる. 最初の 2 つは「位数 16 で, その構造は位数 8 の群と位数 2 の群からなる」という意味であ る. 定理 2.17 より, E(Q)tors ≃ Z/2Z ⊕ Z/8Z と結論出来る. 最後の [[34, 88], [-36, 18]] は生 成元である. 更に楕円曲線 E 上の点を扱ってみよう. 曲線は y 2 + xy = x3 + 2x2 + 4x + 5 を選び P, Q ∈ E ( ) （P = (−1, −1), Q = (1, −4)）をとる. 2 つの点の和 P + Q = − 54 , 15 ∈ E を計算する. 8 gp: E=ellinit([1,2,0,4,5]) gp: P=[-1,-1] gp: Q=[1,-4] gp: elladd(E,P,Q) [-5/4, 15/8] 点のスカラ倍 nP は ellpow(E,P,n) で計算する. 点の位数は gp: ellorder(E,P) 0 となる. P は無限遠点ではないことから, 位数無限の点（即ち, 自由部分の生成元）であることが分 かる. 最後に ap (E) = p + 1 − #E(Fp ) の計算も簡単に出来ることを述べておく. より一般に ak (E) （k ∈ N）を計算する関数が搭載されている. gp: ellap(E,p) gp: ellak(E,k) gp: ellan(E,n) 順に ap (E) のみを出力, ak (E) のみを出力, ak (E)（1 ≤ k ≤ n）を全て出力, という命令である. 実習レポートの提出について 原則として SageMath Cloud を利用して提出すること. 万一 Pari/GP を利用して提出する場合は, 以下の要領で作成すること. • 基本的に解答は全て, 所定の用紙に記入して提出すること. • 1 ∼ 15 は答えのみ解答せよ. • 問題 A∼D は実行プログラムとその実行結果を同封すること. テキストファイルで印刷し ても良いし, 手書きで提出しても構わない. • 問題 E∼G は, 解答する必要はない. 40 参考文献 本稿では, 途中で話題が脱線したり説明不足となるのを避けるため, 最新の学術論文を除き文献の 引用を行わなかった. ここで纏めて書いておく. まず, シラバスに書いた通り 1. J.H. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, GTM 106 (1986). Expanded 2nd Edition (2009). 2. J.H. Silverman and J. Tate, Rational Points on Elliptic Curves, Springer-Verlag, UTM (1992). 3. W. Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer-Verlag, UTM (2009). の 3 編を挙げておく. 最も参考としたものは 1. であるが, 代数曲面論に関する部分などは全く触れ ていない. よりしっかりと理論の背景を知りたい方にお薦めである. 2. は日本語訳も出版されており 2’. 足立恒雄, 木田雅成, 小松啓一, 田谷久雄（訳）「楕円曲線論入門」, シュプリンガー・フェア ラーク東京 (1995), 新版：丸善出版 (2012). に相当する29 . 3. は数式処理システム Sage のチーフデベロッパによる本で, Sage のサンプルコード も多数収録されており読みやすい. なお, この文献は筆者のウェブページから pdf を無償ダウンロー ド出来る. より進んだ内容を学びたいという方には, 1.（及び 2.）の著者による続編 4. J.H. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, Springer-Verlag, GTM 151 (1994). をお薦めする. これについても日本語訳が出版されており： 4’. 鈴木治郎（訳）「楕円曲線論概説」（上・下巻）, シュプリンガー数学クラシックス/丸善出版 (2003, 2012). に相当する. かなりのボリュームがあるが, ぜひ挑戦して頂ければ幸いである. 他にも楕円曲線に関する文献は多数出版されている. 例えば J.W.S. キャッセルズ「楕円曲線入門」 や N. コブリッツ「楕円曲線と保型形式」など, それぞれ特色がかなり異なっているので非常に興味 深い. 是非, お気に入りの一冊を見つけて頂きたい. また楕円曲線暗号に関する文献については, 理論的なものから応用を重視したもの, 技術者向けの ものまで様々あるが, その中でも 5. 辻井重男, 笠原正雄（編）「暗号理論と楕円曲線：数学的土壌の上に花開く暗号技術」, 森北出 版 (2008). がお薦めである. この本は最先端の話題を含みつつも. 数学を学ぶ学生さんにとって最適な作りに なっている. また電子版（無料で手に入るもの）としては 6. 伊豆哲也「楕円曲線暗号入門」. http://researchmap.jp/mulzrkzae-42427/# 42427 が読みやすい. これは伊豆氏の集中講義で使用されたものであり, 書き込みながら手軽に学習できる という意味でも自習用に最適である. 29 そのまま英文タイトルを訳すと「楕円曲線の有理点」となるが, 内容を考慮して変更されている. この記述は, 日本語訳 版の序文にも登場する. 山形大学理学部数理科学科 2014 年度後期「数理情報特選 F/数理科学特別講義 E」講義資料 41 最後に, 本稿を作成するにあたって以下の文献も参考とさせて頂いた. 興味のある方は, これらの 文献にも是非目を通して頂きたい. 勿論, 先に挙げた書籍を参考にしたことは言うまでもない. • 田口雄一郎「有理点の整数論」 http://www2.math.kyushu-u.ac.jp/~taguchi/nihongo/rational.pdf • 田口雄一郎「アーベル多様体と数論」 http://ext-course.math.kyushu-u.ac.jp/Open-Lect/zi liao files/taguchi.pdf • 佐藤篤「コンピュータによる楕円曲線の計算」 http://www.math.tohoku.ac.jp/~atsushi/Jarticle/ec calc.pdf • 木田雅成「代数体上の楕円曲線の計算に関するいくつかの話題」 http://www.ise.chuo-u.ac.jp/TISE/symp/2000/000831w/kida.pdf • 木村巌「数論研究者のための Sage」 http://utomir.lib.u-toyama.ac.jp/dspace/handle/10110/8946 • 富田琢巳「Tate 予想と BSD 予想の幾何学的類似」 http://t-tomita.com/pdf/report6.pdf 謝辞 まずは筆者の本集中講義に際してご尽力賜り, 加えて本稿作成にあたって隅々まで目を通して頂い た上有益なコメントを下さいました, 山形大学の脇克志先生に感謝御礼申し上げます. また, 以下の 九大数理の学生諸氏にはプレセミナーにお付き合い頂き, 数多くのアドバイスを頂戴しました. 合わ せて御礼申し上げます. 池松 泰彦, 井上 公人, 内田 圭亮, 岡本 健太郎, 奥村 伸也, 奥村 喜晶, 草野 元紀, 高田 芽味, Jerome Dimabayao, Cid Reyes. 最後に, 筆者の集中講義に出席し, 忍耐強く真面目に受講して下さった山形大学理学部数理科学科の 学生諸氏に, 心より感謝申し上げます.