院試解答から始まる暗号理論の代数学入門と駄文

　えぇ，この記事は東京大学工学部応用物理系の学生有志一同によるU-TOKYO AP Advent Calendar 2017 - Qiitaなる企画に掲載するための記事です．正直言って何を書くかちゃんと考えないで参加してしまったのですが，Twitterでアンケートを取ったところ*1院試の解答を書けとの声が多数派を占めてしまったので民意に従ってまずはそれから書くことにします．

1. 東京大学大学院情報理工学系研究科2018年度院試解答
- 1.1. 数理情報学専攻2018年度院試第5問解答
- 1.2. その他院試問題の総評
2. 暗号と代数学と数論アルゴリズム
3. 異世界転生をしてみよう~「小説家になろう」の世界~

1. 東京大学大学院情報理工学系研究科2018年度院試解答

　2017年8月に僕は東京大学大学院情報理工学系研究科の大学院入試を受けました．ここのｎを受けるには，TOEFELと2つの筆記試験及び面接を潜り抜けなければなりません．2つの筆記試験は情報理工学系研究科の全専攻共通の数学の試験と専攻ごとの専門科目の試験から成ります．

　専門科目に関しては，僕は数理情報学専攻の専門科目で受験しました．

　……と，まあこんな僕の合格体験記的前書きはどうでも良くて，言いたいことは院試解答として僕が書けるのはTOEFELと共通数学と数理情報学専攻の専門科目ってことですね．他の科目については分かりません．さらに言うと，数理情報学専攻の専門科目の第5問しかちゃんとした解答を書きません．これは，「他の問題についてははっきりと問題文を覚えていない」「第五問は後半の話題（暗号）との関連性が述べやすい」という2つの理由によります．

　では、以下から実際に各問に対する解答を書いていきます（なお、第5問ですら問題文に対する記憶はあやふやなのでもし記憶違いがあってもその点についてはどうかご勘弁のほどを……）

1.1. 数理情報学専攻2018年度院試第5問解答

(1) 整数環 $\mathbb{Z}$ に対してその任意の元 $m,n$ から生成されるイデアルは単項イデアルであり，その生成元は $\gcd(m,n)$ であることを示せ．

(解答)こういうのってどこまでを既知の事実として扱えば良いのかいまいち分からないのですが，とりあえず（そこそこ有名な事実でありますが）整数環が単項イデアル整域であることを最初に示します．つまり，整数環において任意のイデアルが単項イデアル（1つの元から生成されるイデアル）となることを示します．そして，その次に生成元が $\gcd(m,n)$ であることを示します．

　　 $\mathbb{Z}$ の任意のイデアルを $I$ とする．自明なイデアル $I=\{ 0 \}$ である場合は明らかに単項イデアルなので， $I \neq \{ 0 \}$ と仮定します．今，このイデアル $I$ の正の元の中で最小のものを $a$ ，それから生成される単項イデアルを $(a)$ と置きます． $a \in I$ かつイデアルの定義より，明らかに $(a) \subset I$ ．

　一方，任意の $b \in I$ に対して，それを $a$ で割った商を $q$ ，余りを $r$ と置くと，

$\displaystyle b=qa+r ~~( 0 \leq r \lt a)$

が成立する． $r=b-qa$ より $r \in I$ である． $a$ はイデアル $I$ の中で最小の正の元と定義しているので，これより $r=0$ となる．よって $b \in (a)$ となるので， $I \subset (a)$ が示せる．

　以上より整数環における任意のイデアル $I$ が $I=(a)$ ，すなわち単項イデアルとなることが示せた．次に，任意の整数 $m,n$ から生成されるイデアル $J= \{ km+ln | k, l \in \mathbb{Z} \}$ の生成元が $\gcd(m,n)$ であることを示す．

　今， $\gcd(m,n)=c$ ， $J$ の生成元を $d$ と置く（なお $d$ は正とする）． $m,n \in J$ かつ $J$ は $d$ から生成されるイデアルなので， $d$ は $m,n$ の公約数である． $c$ は最大の公約数なので， $d \leq c$ が成り立つ．

　また， $d \in J$ かつ $J$ の定義より，ある整数 $k,l$ を用いて

$d=km+ln$

と表せる．今， $c$ は $m,n$ の公約数なので $m=cm', n=cn'$ と書ける．よって，

$d=c(km'+ln')$

となるので， $d$ は $c$ の倍数である．よって $c \leq d$ となる．

　以上より， $c=d$ が示せた．すなわち，生成元は $c= \gcd(m,n)$ である．

(2) 任意の正整数 $m,n ~~(m \geq n)$ に対して $m$ を $n$ で割った余りを $r$ と置くと $\gcd(m,n)=\gcd(n,r)$ が成立することを示せ．

(解答)高校数学でもみなさん解いたことあるような問題ですね．サービス問題でしょう．すぐ次の問で出てくる「ユークリッドの互除法」の正当性を保証する命題でもあります．計数数理の院試勉強に役立つことで有名な「高校数学の美しい物語」に簡単な証明*2が載っているのでそっちを見てください（丸投げ）．

(3) 任意の正整数 $m,n$ について不定方程式 $km+ln=\gcd (m,n)$ の解 $k,l$ を求める $O(\log m)$ 時間のアルゴリズムを考えろ．

(解答)ユークリッドの互除法をイメージした再帰的アルゴリズムを書けば良いでしょう．以下，再帰の様子を簡単に述べます．まず，対称性より $m \geq n$ として， $m$ を $n$ で割った商を $q$ ，余りを $r$ と置きます．

　ここで， $m=qn+r$ かつ $\gcd(m,n)=\gcd(n,r)$ より，

$km+ln=\gcd(m,n)　\\ \iff k(qn+r)+ln=\gcd(n,r) \\ \iff (kq+l)n+kr= \gcd(n,r)$

となるので，不定方程式 $k'n+l'r= \gcd(n,r)$ の解 $k', l'$ に対して，

$kq+l=k'$
$k=l'$

という関係式が得られる．よって，再帰的に $k'n+l'r= \gcd(n,r)$ を解くことで，その解 $k',l'$ と上記の関係式から，元の不定方程式 $km+ln = \gcd (m,n)$ の解 $k,l$ が得られる．

　以上で，再帰的アルゴリズムにおける再帰の部分の挙動は書けたので，あとはbase case（再帰が終了する場合）について述べれば良いでしょう． $m$ を $n$ で割った余り $r$ が $0$ になったときがbase caseであり，このときは再帰に依らずに直接的に解を求めることが可能です． $m$ を $n$ で割った商を $q$ と置くと，

$m=qn\\ \iff m+(1-q)n=n$

となる．base caseでは $\gcd(m,n) = n$ なので，上式より $(k,l) = (1,1-q)$ が不定方程式 $km+ln= \gcd(m,n)$ の解（の一つ）となります．

　以上のような感じでアルゴリズムを説明すれば解答の大部分は完成したと言えるんじゃないでしょうか．ついでに擬似コードとかを載せても良いかもしれません（僕は擬似コードを書くのは面倒なので書きません）．

　最後に時間計算量が $O(\log m)$ になることを示します．毎回の再帰において余り $r$ がどの程度減るかをざっくり評価するだけです．各再帰において，

$\begin{align*} m &= qn+r\\ & \gt qr+r \\ &\geq 2r \end{align*}$

$\iff r \leq m/2$

が成立するので，余り $r$ は2回の再帰ごとに1/2未満に減少していきます．よって，再帰の回数は $O(\log m)$ 回であることが言えます．*3

(4) 任意の自然数 $p$ に対して，剰余類環 $\mathbb{Z} /{p \mathbb{Z}}$ が体であることの必要十分条件は $p$ が素数であることである．これを示せ．

(解答)代数学の入門書にはほぼ必ず載っている有名な命題ですね．

　まず， $p$ が素数ならば剰余類環 ${\mathbb{Z}}_p$ が体であることを示します．これは今までの小問からの誘導で簡単に解けます． ${\mathbb{Z}}_p$ の $0$ でない任意の元 $a$ に対して，

$ka+lp= \gcd(a,p)$

を満たす整数 $k,l$ が存在することが(1)の問から言える． $p$ が素数ならば $\gcd(a,p) = 1$ なので，上式より，

$ka \equiv 1 \pmod{p}$

が成立する．よって， $k \bmod p$ が ${\mathbb{Z}}_p$ 上の乗法における $a$ の逆元となる．これより ${\mathbb{Z}}_p$ が体であることが示せた

　次に， $p$ が素数でないならば ${\mathbb{Z}}_p$ が体でないことを示す． $p=1$ のときに体でないのは明らかなので*4， $p \neq 1$ とする．このとき $p$ は合成数なので， $1$ でも $p$ でもない正整数 $b,c$ を用いて，

$bc =p$

と表せる．これを ${\mathbb{Z}}_p$ 上の剰余演算として表すと，

$bc \equiv 0 \pmod{p}$

となる．仮に $b$ が逆元 $b^{-1}$ を持つとすると，上式の両辺にそれをかけて，

$c \equiv 0 \pmod{p}$

が得られる．しかし，これは $c$ が $p$ の $p$ 自身とは異なる約数であるという仮定に矛盾する．よって， $b$ は逆元を持たない．逆元を持たない元が存在するので ${\mathbb{Z}}_p$ は体でない．

　以上で， ${\mathbb{Z}}_p$ が体であることと $p$ が素数であることとの同値性が示せました．この体 ${\mathbb{Z}}_p$ は次章以降でも出てくるので一応覚えておいて貰えると嬉しいです．

(5) すみません。問題内での正確な数値は忘れました．具体的に（手計算できる程度に巨大な）素数 $p$ と正整数 $a$ が与えられ， ${\mathbb{Z}}_p$ 上の乗法における $a$ の逆元を求めよ，という形の問題文でした．

(解答)前問の解答をヒントにすれば，不定方程式 $ka+lp=1$ を解けば良いだけだとすぐ気付くはずです．不定方程式の解き方は(4)のアルゴリズムがヒントになってて，実際にユークリッドの互除法を実行すればすぐ解けます．この不定方程式の解法の詳細も「高校数学の美しい物語」に載っていたので解説はそっちに丸投げします．*5

1.2. その他院試問題の総評

　一応，他の問題に関しても記憶の覚えている限りで簡単に述べたいと思います．この手の合格体験記みたいな記事を書くのはあまり好きじゃないんですが何も書かないと「Twitterでのアンケートを無視するのか！！」と（主に学科民たちから）怒られそうなので……（）．と言っても，TOEFEL-ITPに関しては特に僕のほうで何かコメントすることもないので割愛します．巷に溢れている問題集などを読んだ方が良いです（元も子もない発言）．

　続いて情報理工学系研究科の全専攻共通科目である数学について述べます．例年，共通数学は大問3つから構成されており，第一問が線形代数，第二問が解析，第三問が確率に関する問題になっています．

　共通科目第1問の線型代数では過去問の傾向と大幅に変わり，固有値を計算して対角化させるだけの問題は出題されず，連立一次方程式が解を持つ条件と行列のランクの関係や重回帰分析に関する問題などが出題されました．さらに，この第1問にて今年度の院試最大の鬼門であるムーア・ペンローズの擬似逆行列の存在と一意性を証明する問題が出ました．あらかじめ予想して証明を勉強しておけば解けたのかも知れませんが，ここまで大幅な傾向変更は正直予想不可能でしたね（）．ムーア・ペンローズの擬似逆行列の定義とその一意存在証明についてはここで書くのも面倒なので適当に調べてください（丸投げ）

　共通科目第2問は解析に関する問題だったけど正直どんな問題だったか忘れました．なんか収束性の証明がきつい問いがあった記憶があります．ちょっとマジで問題を覚えてないので何も書くことないです．
　
　共通科目第3問は，ある確率過程が与えられてその漸化式や色んな期待値などを求める問題が出題されました．これも申し訳ないことに具体的な確率過程の内容を忘れたのですが，難易度的には高校数学の確率漸化式のノリで解けます．今年の共通数学の大問の中で完答を狙うとしたらこの問いでしょう．ただし，後半のほうは少し計算が面倒で，時間との勝負感がありました．

　専門科目の方は先述の通り数理情報学専攻の科目で僕は受験しました．数理情報学専攻の科目は全部で大問が5問ありその中から3つをだけ選択して解答する形式になっています．僕は第2問，第4問，第5問の3つを選択したので，第1問と第3問については特にコメントできません．*6

　数理情報学専攻第2問は確率に関する問題が出ました．(1)は正規分布の密度関数をもとに愚直に計算していけば答が出ますが，(2)以降は割と難しめの証明問題でした．どんな命題だったか忘れたうえ，正直解けてないので詳しいことは言えないです．すみません…

　数理情報学専攻第4問は力学系に関する問題でした．あるシステムを記述する微分方程式が具体的に与えられ，(1)ではその微分方程式の定常解を解かされました．その後，小問の誘導に従ってそのシステムにおけるリアプノフ関数を見つけ，そのリアプノフ関数の性質から定常解の安定性などを考察するような問題でした．リアプノフ関数という名称を知らなくても，誘導に従って微分方程式を計算していけば解答はできると思います．

　数理情報学専攻第5問については解答をすでに上の章で記述したのでここでは詳述しません．（線型代数以外の）抽象代数学に関する問題が出たのは数理情報学専攻の入試ではかなり久しぶりだった（というかここ10年ほどの中では実質初めて）ので敬遠した人も多いようですが，問題自体は高校数学でやるような整数論の延長みたいな議論で解けます．「単項イデアル」とか「体」とかの定義をちゃんと覚えていれば難しくはないでしょう．

2. 暗号と代数学と数論アルゴリズム

　この章では暗号理論と代数学の関係及びそこで用いられるいくつかのアルゴリズムを紹介したいと思います．ほぼ初心者向けに書くのであまり難しい用語を説明なしで使うことはしないようにするつもりです．また，僕の趣味で書くため僕が好きな分野の大雑把な紹介程度に留まると思います．

2.1. 代数学の用語説明

　前章で解説した数理情報学専攻院試第5問の解答ですが，代数学をちゃんと勉強したことない人にとっては良く分からない言葉が多くて意味不明だったかもしれません．「整数環ってなんや？イデアルってなんや？体ってなんや？」と思った人は少なくないでしょう．代数学は数学における重要な一分野を成していますが，数学の他の分野に比べると初学者が最初に覚えなきゃいけない用語や定義が多めです．そこが代数学のつらいところではあるんですが，どうしても避けて通れない場所なので説明します．とりあえず本記事では群・環・体までは説明の必要があるので一気にしてしまいます．

演算
集合 $G$ に対して写像 $f: G \times G \to G$ を $G$ における「（二項）演算」と呼ぶ．演算 $f$ はしばしば記号 $``\cdot"$ を用いて，

$f(a,b) = a \cdot b ~~~~~(a,b \in G)$

と表記することが多い．

群
以下の3つの条件を満たす演算 $`` \cdot "$ を備えた集合 $G$ を「群」と呼ぶ．

$\forall a,b,c \in G$ に対して， $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ が成立する（これを「結合法則」と呼ぶ）．
単位元と呼ばれる元 $e \in G$ が存在し， $\forall a \in G$ に対して $a \cdot e = e \cdot a = a$ が成立する．*7
$\forall a \in G$ に対して逆元と呼ばれる元 $a^{-1} \in G$ が存在し， $a \cdot a^{-1} = a^{-1} \cdot a = e$ が成立する．*8

また， $\forall a, b \in G$ に対して， $a \cdot b = b \cdot a$ が成り立つとき（これを交換法則と呼ぶ），その群を特別に「可換群」と呼ぶ．*9

環
集合 $R$ に対して定義される， $`` + "$ と $`` \cdot "$ で表記される2つの演算（それぞれ「加法」と「乗法」と呼ぶ）が以下の条件を満たすとき， $R$ を「環」と呼ぶ．

$R$ は加法に関して可換群を成す．（なお，加法に関する単位元を $``0"$ ， $a \in R$ の加法に関する逆元を $``-a"$ と表すことが多いです）
$R$ は乗法に関して結合法則を満たす．
$R$ は乗法に関して単位元を持ち，その単位元をしばしば $``1"$ と表記する．*10
$\forall a,b,c \in R$ に対して， $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ かつ $(a + b) \cdot c = (a \cdot c) + (b \cdot c)$ を満たす（これを「分配法則」と呼ぶ）．

体
環 $F$ は以下の条件を満たすとき「体」と呼ばれる．

$F \setminus \{ 0 \}$ が乗法に関して可換群を成す（つまり，環の乗法に対する条件として逆元の存在と交換法則の2つが加わった）．
$1 \neq 0$ である（つまり，乗法の単位元と加法の単位元は異なる）．*11

この群・環・体の3つについては定義がややこしいですが一応飲み込んでください．馴染みのある具体例を挙げるならば環は「整数」，体は「有理数」や「実数」などをイメージすると良いでしょう．

2.2. 有限体と離散対数問題

　
　有限体とは文字通り「有限個の要素しか持たない体」のことです．「ガロア体」という別名もあります．暗号理論では有限体というのは非常に好まれます．何といっても有限集合なので計算機上で扱いやすいのです．

　前章で解説した院試問題第五問(4)において， ${\mathbb{Z}}_p$ は $p$ が素数の時に体となることを証明しました．一般に剰余類環 ${\mathbb{Z}}_p$ とは， $\{0, 1, \cdots, p-1 \}$ から成る集合で，加法や乗法などの演算は $\bmod p$ の上で定義されていると考えてください*12．代数学の世界では群や環などにおける集合の要素数を「位数」と呼ぶのですが，実は有限体の位数は素数 $p$ と正整数 $n$ を用いて $p^n$ と必ず表せることが証明できます（面倒なのでここでは証明は書きませんが）．そして，誤解を恐れずに大雑把に感覚的な表現をするならば*13，位数 $p^n$ の有限体は一般にベクトル空間 ${\mathbb{Z}_p}^n$ と似たようなものとみなすことができます．つまり，第5問(4)で出てきた $\mathbb{Z}_p$ は有限体の一番分かりやすい代表的な例だったのです．なので，有限体を扱うことの多い暗号理論でもこの $\mathbb{Z}_p$ について色々と考察することがあります．

　例えば， ${\mathbb{Z}}_p$ の有名な性質の1つとしてその乗法に関する群が巡回群になっているというものがあります．「巡回群」とは，群 $G$ のある元 $g$ *14の整数乗の形で他の任意の元を表せるような群のことを指します．つまり，ある ${{\mathbb{Z}}_p} \setminus \{ 0 \}$ の元 $g$ が存在し， $\forall a \in {{\mathbb{Z}}_p} \setminus \{ 0 \}$ に対して，ある整数 $n$ を用いて，

$a \equiv g^n \pmod{p}$

が成立するということです．ここから ${\mathbb{Z}}_p$ 上の乗法に関する離散対数問題を考えることができます．離散対数問題とは，巡回群 $G$ についてその生成元 $g$ と $a \in G$ が与えられたときに， $a=g^n$ となるような整数 $n$ を求める問題のことです*15．

　離散対数問題は暗号理論においては色々なところで出てくる頻出問題なのですが，この ${\mathbb{Z}}_p$ 上での離散対数問題が最も一般的かつ有名で，これを解くためのアルゴリズムがたくさん発見されています．これら離散対数アルゴリズムを全部紹介すると記事がめちゃくちゃ長くなるので控えますが，その中でもわりと有名なρ法についてだけ簡単に紹介します*16．簡単に，と言いつつ少し長くなるのですがご勘弁ください*17．

　と言っても，実を言うとρ法だけでは ${\mathbb{Z}}_p$ 全体の生成元 $g$ を底とする離散対数は求められません*18．ρ法は，ある ${\mathbb{Z}}_p$ の元 $\gamma$ を生成元とする巡回群 $\{1, \gamma, {\gamma}^2, \cdots , {\gamma}^{q-1} \}$ の位数 $q$ が $p-1$ の素因数であるときに，その $\gamma$ を底とする離散対数を計算することができるアルゴリズムです．証明はしませんがこのような $\gamma$ の存在は必ず言えます．
　
　ρ法は擬似ランダム関数 $F : \{ 1, \gamma, {\gamma}^2, \cdots , {\gamma}^{q-1} \} \to \{ 0, 1, \cdots , q-1 \}$ を用います．擬似ランダム関数とは，その名の通り「一様ランダムに値を出力しているように見える関数」のことです．以下にρ法の擬似コードを記します．

input :  p,  q,  g,  a　

i = 1 ;   x = 0 ;   b = a ; 
y = F(b) ;   c = b*a*(g^F(b)) mod p ;


while b != c do

   x = x + F(b)  mod q ;
   b = b*a*(g^F(b)) mod p ;

  for j = 0  to 1  // ようは以下の作業を2回繰り返す
     y = y + F(c) mod q ; 
     c = c*a*(g^F(c)) mod p ;
  end

  i = i+1

end


if i < q then
 return (x - y) / i mod q ;

else return "fail" ;

　上記コードの入力におけるgは素数位数 $q$ の巡回群を生成する元 $\gamma$ を表してます（gammaと書くと長いので略しただけです）．このアルゴリズムによって出力される値は"fail"でない場合は $a \equiv {\gamma}^n \pmod{p}$ を満たす整数 $n$ に一致します．以下，このアルゴリズムの正当性を簡単に示します．whileループ中の各繰り返しにおいて，

$b \equiv {{\gamma}^x}{a^i} \pmod{p} \\ c \equiv {{\gamma}^y}{a^{2i}} \pmod{p}$

が成立します． $b=c$ のときにwhileループを抜けるので，このとき

　 ${\gamma}^{x-y} \equiv a^i \pmod{p}$

が成立しています．よって， $i \lt q$ ならば上記のアルゴリズムによる出力は正しい離散対数になります．

2.3. 楕円曲線と暗号

　前節では有限体 ${\mathbb{Z}}_p$ 上の離散対数問題について見ましたが，最近の暗号理論界隈では「有限体上の楕円曲線」における離散対数問題が流行りのようです．楕円曲線を利用した暗号は（そのまんまですが）「楕円曲線暗号」と呼ばれています．

　「有限体 $F$ 上の楕円曲線 $E(F)$ 」とは，

$E(F) = \{ (x, y) \in F^2 : y^2 = x^3 + Ax + B \} \cup \{ O \} ~~~~~(A, B \in F)$

という集合のことを表します*19．上式における足し算や掛け算は普通の足し算や掛け算ではなく有限体 $F$ において定義されている加法や乗法であることに注意してください．また， $O$ はいわゆる「無限遠点」と呼ばれる特別な点になります．

　実を言うと楕円曲線は体 $F$ が必ずしも有限体上でなくても構わなくて，一般の体に対しても同様に定義できます．「楕円曲線」というキーワードで画像検索すると「膨らんだ餅を横に倒したような形のグラフ」がたくさん出てきますが，あれは実数体 $\mathbb{R}$ （当然有限体ではない）の上で定義された楕円曲線の図です．

　一方，有限体上の楕円曲線は「曲線」という名前がついてはいるもののあくまでも有限集合です．なんとなく幾何学的なイメージをするならば，ググるとたくさん出てくる実数上の楕円曲線の図において，それらの曲線が格子点上にのみ点を取り，なおかつその格子点の範囲が一定の領域に制限されている図をイメージすると良いでしょう．

　以下の段落では有限体上の楕円曲線における加法演算の定義を説明しますが，厳密な定義を書くのは面倒なので多分に幾何学的なイメージを要求されるような大雑把な説明に留めます．なので，今言ったようなイメージで脳内に有限体上の楕円曲線を描きながら以下の文章を読んでください（それがイメージしにくい人は実数上の楕円曲線の図を頭に思い浮かべても構いません．幾何学的なイメージとしてはそっちのほうが恐らく分かりやすい気がしますし）．

楕円曲線における加法

　有限体 $F$ 上の楕円曲線 $E(F)$ において相異なる2点 $P, Q \in E(F)$ が与えられたとき， $P$ と $Q$ を結ぶ直線と $E(F)$ との（ $P$ や $Q$ とは異なる）交点の座標を $(x,y)$ としたときの点 $(x, -y)$ を $P+Q$ の点として定義します．このような楕円曲線上の点 $P+Q$ は $P$ と $Q$ が $x$ 軸に関して対称でない限りは必ず存在することが示せます（証明は略します）．

　もし $P$ と $Q$ が $x$ 軸対称な場合は，特別な無限遠点 $O$ を用いて $P+Q=O$ と定義します．また，任意の点 $P$ に対して $P+O=O+P=P$ と定義します．つまり，無限遠点 $O$ は楕円曲線上の加法に関する単位元であり， $P$ の楕円曲線上の加法に関する逆元 $-P$ は $P$ の $x$ 軸対称な点になります．

　最後に， $P$ と $Q$ が同じ点のときの加法，すなわち $P+ P = 2P$ を定義します．点 $P$ における楕円曲線 $E(F)$ の接線と $E(F)$ との交点の座標を $(x, y)$ としたときの点 $(x, -y)$ が $2P$ の点として定義されます．

　こうして，「2点を結ぶ直線と楕円曲線との交点」という大雑把な幾何学的なイメージのもとで楕円曲線上の加法を定義しました．これも証明は省きますが，楕円曲線 $E(F)$ はこの加法に関して可換群を成すことが示せます．そして「楕円曲線上の離散対数問題」とは，楕円曲線上の2点 $P, Q$ が与えられとき，楕円曲線上の加法において，

$Q = nP$

を満たす整数 $n$ を求める問題のことです．

楕円曲線暗号の例

　さて，ここまでは良く分からない代数学上の概念がたくさん出てきただけで「暗号と何が関係あるのか分からない」という人も多かったかもしれません．なので，実際に楕円曲線を使った暗号の一例として楕円曲線 ElGamal暗号をこの節で紹介します．

　暗号理論の世界において暗号方式を説明する際には「アリスとボブという2人の人間の間でメッセージをやり取りする」という設定の下で説明することが多いのでここでもその設定を採用します．そして，アリスとボブの間のメッセージのやり取りをイブという人が盗聴しようとしている設定です．アリスとボブは盗聴者であるイブにメッセージの内容を知られたくありません．

　先述のように暗号理論では基本的に「有限体上の楕円曲線」を使うことが多いので今回アリスとボブもそれを使います．有限体を使うのは有限ゆえに計算機上で扱いやすいためです．具体的には先述のような ${\mathbb{Z}}_p$ を有限体としてイメージしてください．そしてこの有限体の上で適当に決められた楕円曲線を $E$ とします．そして， $E$ 上の点 $G$ を選び，楕円曲線上の加法演算において $nG=O$ となる最小の正整数 $n$ を計算します．これら $(E, G, n)$ は公開パラメータです．公開パラメータということはアリスとボブだけでなくて盗聴者イブもパラメータの値を知っているということです．それでは，この公開パラメータの下での楕円曲線 ElGamal暗号の手順を説明します．

①ある日ボブに秘密のメッセージを送って欲しいと思ったアリスは，秘密鍵として $s \in \{ 1, \cdots , n-1\}$ を決めます．この秘密鍵 $s$ はボブにも教えずにアリスの心の中だけに閉まっておきます（つまり，盗聴者イブもこの秘密鍵は知りません）．そして，アリスは楕円曲線 $E$ 上で $Q=sG$ を計算しこの $Q$ をボブに伝えます．しかし，アリスとボブの間の会話を盗聴しているイブにもこの $Q$ の値は知られています．

②アリスから $Q$ を受け取ったボブは，これを使ってアリスにメッセージ $m \in E$ を送ろうと考えます．しかし，そのまま送ると盗聴者イブにもメッセージがバレるので， $Q$ を使ってメッセージ $m$ を暗号化してからアリスに伝えなければなりません．そこで，まずボブは乱数 $r \in \{ 1, \cdots ,n-1 \}$ を選びます．この $r$ はアリスにも直接伝えずにボブの心の中に閉まっておくので盗聴者イブも知ることができません．

③ボブは楕円曲線 $E$ 上で $C_1 = rG$ と $C_2=m+rQ$ を計算し， $(C_1, C_2)$ の組を暗号文としてアリスに伝えます．このとき，イブも盗聴しているのでイブも暗号 $(C_1, C_2)$ の値は知っています．

④ボブから暗号文 $(C_1, C_2)$ を受け取ったアリスは秘密鍵 $s$ を使って，ボブからのメッセージ $m={C_2} - s{C_1}$ を複号します（この計算式でメッセージが複号できることはこれまでの手順を見れば自明でしょう）．

　以上が楕円曲線 ElGamal暗号の方式です．この方式において盗聴者イブが盗聴で知ることが出来るのは公開パラメータ $(E, G,n)$ と $Q, C_1, C_2$ だけです．ここで，もしイブが楕円曲線上の離散対数問題を簡単に解くことができると仮定すると，イブは

$Q=sG$

を満たす秘密鍵 $s$ を簡単に計算できるので，この秘密鍵を使ってアリスと同様の複号方法でメッセージ $m$ を知ることができてしまいます．つまり，この楕円曲線 ElGamal暗号は安全ではなくなるのです．このことから楕円曲線 ElGamal暗号が安全であるためには「楕円曲線上の離散対数問題が難しいこと」が必要条件であると言えます．暗号理論において離散対数問題の解法がたくさん研究されてきたのはこのような理由によるものです．*20

2.4. RSA暗号と素因数分解

　恐らく世間的には楕円曲線暗号よりもRSA暗号のほうが有名でしょう．このRSA暗号も第1章で解説した数理情報学専攻院試問題第5問の内容と多少絡めることが出来るので紹介します．前節と同様に，アリスとボブの2人の間のやり取りという形で解説します．

RSA暗号

①ボブからのメッセージが欲しいアリスは２つの巨大素数 $p,q$ を決めます．この素数の値は公開しませんが，代わりに $n=pq$ を公開します．

②次にアリスは $\phi(n)=(p-1)(q-1)$ を計算し， $\phi(n)$ と互いに素な $\phi(n)$ 未満の正整数 $e$ を適当に選びます．そして， $e$ も公開します（ $\phi(n)$ の値は公開しません）．

③アリスはさらに $ed \equiv 1 \pmod{\phi(n)}$ を満たすような正整数 $d$ を計算しておきます*21．この $d$ は公開せずに秘密鍵としてアリスが持っておきます．

④公開鍵として $n, e$ を受け取ったボブは，これを使ってメッセージ $m \in \{1, \cdots ,n-1 \}$ を暗号化します．具体的には， $c=m^e \bmod n$ を計算してこの $c$ を暗号としてアリスに送ります．

⑤ボブから暗号 $c$ を受け取ったアリスは，秘密鍵 $d$ を使って $m = c^d \bmod n$ を計算することでメッセージを複号します．*22

　これがRSA暗号と呼ばれる暗号方式です．こっちのほうは手順だけみると代数学というよりはもっと単純な整数論の内容だけで理解できるので，恐らく知っている人が多いのだろうと思います．さて，この暗号においても盗聴者イブは存在します．盗聴者イブが盗聴で知ることのできるパラメータは公開鍵である $(n,e)$ と暗号 $c$ だけです．仮にイブが素因数分解を簡単に解くことができると仮定します．するとイブは，

$n=pq$

となる素数 $p, q$ を計算できるので，これから $\phi(n)=(p-1)(q-1)$ を経由してアリスと同様の手順で秘密鍵 $d$ を手に入れることができてしまいます．こうしてイブはこの秘密鍵から暗号文 $c$ を複号できてしまうので，RSA暗号は安全でなくなってしまいます．つまり，RSA暗号が安全であるためには「素因数分解が難しいこと」が必要条件として言えるのです．

素因数分解とアルゴリズム

　上記のような理由で，暗号理論の世界では素因数分解の解法の研究もかなり重要な内容になっていました．離散対数問題と同様に素因数分解のアルゴリズムも色々と開発されています．

　1章の数理情報学専攻第5問の解説にて触れられた「ユークリッドの互除法」は2数 $m,n$ の最大公約数 $\gcd(m,n)$ を求めるアルゴリズムですが，2数の最大公約数を求めるにはもう1つ簡単に思いつく方法があります．そう， $m,n$ をそれぞれ素因数分解して，共通の素因数を掛け合わせる方法です．この事実は，素因数分解アルゴリズムと最大公約数アルゴリズムの間の帰着を与えていることになるので，素因数分解は最大公約数問題以上に難しいと言うことができます*23．

　さて，ユークリッドの互除法の計算量が $O(\log m)$ であることは第1章で示した通りです．暗号理論では，入力された整数を $m$ とするときその桁数（すなわち， $\log m$ ）をパラメータとして考えることが多いのですが，その考えに基づくとユークリッドの互除法は桁数に対して多項式時間のアルゴリズムを与えていると言えます．つまり，最大公約数は桁数に対して多項式時間で求めることが可能という訳です．では，最大公約数問題以上に難しい素因数分解に対しては果たして多項式時間のアルゴリズムは存在するのでしょうか？実はこれは未解決問題であり真偽どちらも証明できていないのですが，多くの研究者は恐らく「多項式時間では素因数分解は解けない」と予想しています．

　という訳で素因数分解を多項式時間で解くアルゴリズムは依然として発見されていないのですが，多項式時間に限らなければいくつものアルゴリズムが発見されています．そんな素因数分解アルゴリズムの一例としてρ法を最後に紹介してこの章を終わりにします．

　素因数分解のρ法は，離散対数問題の解法としてすでに紹介したρ法と本質的には同じアイディアに基づいています．ρ法1回だけでは $n$ の素因数分解をいきなり求めることはできませんが，入力として合成数 $n$ を与えられたときにその非自明な因数 $d$ を1つ発見することはできます．ρ法で $n$ の因数が発見できたら，その因数で $n$ を割った値や発見された因数に対して再びρ法を適用する，という手順を再帰的に繰り返すことで $n$ の素因数分解を求めることができます．離散対数問題のρ法と同様に素因数分解でのρ法でも擬似ランダム関数 $F : \{ 1, \cdots , n-1\} \to \{1, \cdots ,n-1 \}$ を用います．

Input: n

x = 2 ;  y = F(x) ;  d = gcd(|x-y|, n) ;

while d = 1 do
  x = F(x) ; 
  y = F(F(y)) ;
  d = gcd(|x-y|, n) ;
end

if d < n return d ; 

else return "fail" ;

　上記がρ法のアルゴリズムです．このアルゴリズムの正当性は自明なので説明しなくても良いでしょう．素因数分解のρ法も，先に紹介した離散対数問題のρ法も，次のアイディアを共有しています．それは， $x$ と $y$ が擬似ランダム関数に従って更新されていくとき，片方は1つずつ更新され行くのに対してもう片方は1つ飛ばしで更新されていくという考えです.つまり，アルゴリズム中の各繰り返しにおける $x$ と $y$ の値の変化を添え字 $i$ を用いて, $x_i, y_i$ と表したとき，

$y_i = x_{2i}$

が成立しているという意味です．この事実と， $F$ のランダム性に関するヒューリスティックな仮定の2つから，ρ法の再帰回数の期待値を見積もることができます．詳細な説明は省きますが， $F$ に関するかなりヒューリスティックな仮定の下で「誕生日のパラドクス」などの考えを用いると，上記の素因数分解のρ法の再帰回数は高い確率で $O(n^{1/4})$ になることが言えます．

3. 異世界転生をしてみよう~「小説家になろう」の世界~

　記事タイトルにある「駄文」の部分がこの章になります．Twitterのアンケート*24にて「なろう小説について語れ」との声が院試解答に次いで2番目に多かったので書かざるを得なくなった感じです（？）．

　と言っても，すでにこのU-TOKYO AP Advent Calendar 2017 - Qiitaの企画では14日目に領民氏が「小説家になろう」について存分に語ってくれています*25．「‟なろう小説”ってなんじゃい」「どんな小説があるの？」という人はそちらをぜひ参考にしてください．この記事では「なろう小説」の典型的ジャンルの一部を構成する「異世界転生」と「現代知識チート」という2つの要素についてオタク語りをしていこうと思っています．

　なろう小説を何作も読んだことがある人は分かると思いますが，「小説家になろう」では圧倒的多数の作品において主人公が異世界に行きます．異世界への行き方は大きく分けて転移か転生の2種類です*26．そして，異世界に来た主人公は何らかの「チート」能力を持つことが多いです．大体の主人公は転生の際に神様から何かしらの理由で魔法や身体能力などにおいて「チート」級の強さを与えられたり特殊能力を貰ったりしますが，それがなくても異世界でチートする主人公もいます．そう，「現代知識チート」と呼ばれるやつです．

　しばしば「中世ヨーロッパ風ファンタジー世界」として描写される異世界では，現代日本で用いられているような高度な科学技術は存在していないことが多いです．そこで，主人公はそんな異世界に現代世界の科学技術を持ち込むことで異世界無双ができると言うわけです．なろう小説における現代知識チートには色々なパターンがあります．農業技術や経済制度の改革を異世界の国王などに進言することで異世界の経済を豊かにさせたり，現代日本では有り触れているが異世界人にとっては未知であるような商品を開発して商売で一儲けしたり……etc

　どんな現代知識チートを見せるかは作者の腕の見せ所でもあるのですが，そこで重要なのが主人公の設定です．冷静に考えれば分かることですが，普通の平凡な設定の主人公だと現代知識チートできるだけの知識をそもそも持っていないでしょう．もちろん平凡な主人公でも現代知識で活躍できるよう異世界の技術レベルを大幅に下げる設定を設けることも可能です*27．しかし，良くある「なろう小説」の舞台である「中世ヨーロッパ風のファンタジー世界」ではもう少し文明が進んでいることが十分予測できるでしょう．だからこそ，主人公が現代知識チートできるようになるためには主人公側もある程度の専門家である必要があるのです．例えば，医者や医学部生の主人公が異世界転生して医学の知識を異世界人に授けるというパターンはその典型です．医学知識チートはなろうに限らず現代知識チートものの作品では昔から良く見るパターンですが，大抵は主人公にそれなりの医学知識がある設定となっています．つまり，「異世界で現代知識チートするためには主人公が何らかの専門知識を持っている」必要があるわけです．

　実を言うと，異世界転生したときの現代知識チートのやり方を分野別にまとめた著作が出版されています．山北篤著『現代知識チートマニュアル』（新紀元社）という本です．この著作は，異世界転生したときに使えそうな現代知識を医学や化学，政治や経済など各分野別にまとめたものです．「小説家になろう」で現代知識チート型異世界転生ものを執筆したい人にとっては非常に参考になる一冊だと思われます．

　さて，自分の専攻を持っている‟大学生なろう読者”ならばここまでの話を聞いたところで恐らく一度は「はたして自分の扱っている専門分野は異世界転生したときに使えるのだろうか？」という疑問を抱くでしょう．この記事は東京大学工学部応用物理系の有志一同によるU-TOKYO AP Advent Calendar 2017 - Qiitaへの寄稿記事であり，また僕自身も東京大学工学部応用物理系の計数工学科数理情報工学コースに属する学生でもあります．というわけで，「東京大学工学部応用物理系の専門分野は異世界転生での現代知識チートに使えるのか」をテーマに語って，この章を締めくくりたいと思います．

　と言っても，僕は東大工学部応用物理系の2学科のうち物理工学科のほうについては詳しく知りません*28．ということで，僕の所属する東京大学工学部計数工学科についてのみ考えます．計数工学科は色んな研究分野があるので，異世界でも何かしら役立つ研究は多そうです．しかし，計数はわりと情報系寄りの学科なので，役立てるのがなかなか難しい分野も結構ありそうです．例えば，異世界には恐らく高確率で（現代日本にあるような）高性能の電子計算機は存在しません．なので，単純なプログラミング技術自体は使えないことが多いでしょう．もちろん，異世界で一からコンピュータを発明するという力業は不可能ではないのかもしれませんが，かなり難しいのは想像に難くないでしょう．同様の理由で，計数でたくさん行われているような電子工作技術も，異世界で使用するにはそれだけじゃなかなか難しいところがあります．

　しかし，これらの技術がそのままでは異世界で役立たないからと言って，「仮に異世界転生しても自分は活躍できない」と悲観することはないでしょう*29．それらの知識も理論面では役立つことが大いにあるかも知れません．計算機科学の理論的な側面や個々の色々なアルゴリズムの中には，現代のような高性能なコンピュータがなくても有用なものは多いはずです．そもそも現実の歴史から類推するに，中世ヨーロッパ風の異世界ならば電子計算機はなくてもアナログな計算機や機械式計算機は存在する可能性はそれなりにありそうです．少なくともソロバンや計算尺ぐらいならば異世界にも存在する可能性が高いですし，もし異世界にそれらがないとしても，その場合はそれら計算機を発明するだけでも十分に「現代知識チート」ができたと言えるでしょう．また，例えば基数ソートみたいに，中世レベルのからくり式の計算機でも実装できそうなアルゴリズムは存在します．たとえそれらを自分で一から直接作るのは難しくても，理論的枠組みやアイディアを与えるだけでも十分に活躍できそうに思えます．

　自分は計数工学科の中でも数理情報工学コースに現在は所属しているので，そちらのコースの専門のほうを特に念頭に入れて考察しているのですが，数理情報工学コースで扱う知識の中で一番‟手軽に”異世界でも役立ちそうな知識は何だろうと考えたときすぐに思いついたのはやはり統計学関連の知識ですね．異世界の統計学がどのように発展しているのかは想像に任せるしかありませんが，基礎的な種々の仮設検定やパラメータ推定の方法を伝授するだけでもだいぶ重宝されそうな気がします．異世界の王国などで社会や経済の調査をしたい国王や大臣にそういう手法を提案するだけでもだいぶ「内政チート」感は演出できるのではないでしょうか．

　以上，とりとめもなくつらつらと「異世界転生」と「現代知識チート」について語りました．現代知識チート系の「なろう作品」の中で僕の一番のお勧めは『異世界薬局』ですね．僕が医療関連の知識にかなり疎いので作中の医療や薬学ネタがどの程度正確なのかは何とも判定しがたいのですが，作品自体はなかなか面白くて読み応えあると思います．暇があればぜひ読んでみることをお勧めします．

*1:https://twitter.com/President_tener/status/939030087780810752

*2:ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語

*3:なお，ユークリッドの互除法の再帰回数についてはより正確な上界を求めることができます．詳しくは「ラメの定理」で検索してください

*4:厳密にはこれは体の定義次第では正しくなくなるのですが，この記事では $1 \neq 0$ も体の定義に含めることにします（そうしないと示すべき命題がそもそも成立しないので）

*5:ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語

*6:一応簡単に内容だけ触れると，第1問では半順序集合と束論絡みの問題が，第3問では最適化に関する問題が出ていたそうです

*7:なお，単位元は存在するとすれば一意であることが容易に示せます

*8:なお，ある元に対して逆元が存在するならばそれは一意に定まることが容易に示せます

*9:「アーベル群」と呼ぶこともあります

*10:流派によっては乗法単位元の存在を環の定義に含めないこともありますがこの記事ではその流派を採用しません

*11:これを体の定義に含めない流派もありますがこの記事ではその流派は採用しません

*12:本当は $\mathbb{Z} / p \mathbb{Z}$ として表される商集合として定義すべきなんですが，ここでは説明を簡単にするためこのように定義してます

*13:ここら辺の詳細に興味がある人は「体の拡大」などをキーワードに調べてください

*14:これを一般に「生成元」と呼びます

*15:一般の群において $g^n$ とは $g$ を $n$ 回‟掛ける”ことを表しています．この場合の‟掛け算”は群 $G$ 上での演算です

*16:ちなみに，ρ法自体は ${\mathbb{Z}}_p$ に限らず，一般の巡回群に対しても拡張可能なアイディアです

*17:なお，今から説明するρ法についてはV.Shoup氏によるA Computational Introduction to Number Theory and Algebraを大いに参考しました．というか，そこからのほぼ引用です．詳細を知りたい人は是非そちらを読んでください

*18:それを求めるには，まず $p-1$ を素因数分解して，次にそれぞれの素因数の冪乗を位数とする巡回群の生成元を見つけて，その各生成元に対してρ法適用例をbase caseとする再帰的アルゴリズムを適用し，中国人剰余定理を用いて離散対数を計算するというわりと長いステップが必要になります．ちなみに，素因数分解は一般にとても難しいと予想されているので，そのことが ${\mathbb{Z}}_p$ 離散対数問題の計算量的な困難性を保証しています

*19:本当は体 $F$ の標数が小さいときはこの定義は正しくないのですが，暗号理論では有限体の標数 $p$ はとてつもなく巨大な素数であることが多いので上式の定義でも問題ないことになります

*20:ちなみに，ElGamal暗号自体は楕円曲線に限らず一般の巡回群においても定義することができます．そして，それぞれの群の形に応じて離散対数問題のバージョンもまた異なるので色んなバージョンの離散対数問題の解法がこれまでに研究されて来ているのです．先に紹介した ${\mathbb{Z}_p}$ 上の離散対数問題の解法もその一例です

*21:このような $d$ を求めるには不定方程式 $de + k \phi(n) = \gcd(e, \phi(n) )$ を解けば良く，これが解けることは当記事第1章の数理情報学専攻第5問(3)で解説した通りです

*22:これで正しくメッセージを複号できることは一見自明ではないですが，フェルマーの小定理を使うとわりと簡単に証明できます．

*23:帰着とかいう概念が良く分からない人は「計算複雑性理論」辺りをキーワードに調べてください．簡単に大雑把なイメージを説明すると，「素因数分解を簡単に解けるならば最大公約数も簡単に求まる」という事実の待遇を取って，「最大公約数が簡単に求められない（つまり難しい）ならば素因数分解も難しい」という事実が言えるということです．

*24:https://twitter.com/President_tener/status/939030087780810752

*25:解析力学、量子力学と群論、そして「小説家になろう」 - 領民のブログ

*26:なろうと言えば異世界転生，という印象の読者は多いでしょうが体感としては異世界転生ではなく異世界転移ものも同じぐらいあります．両者は厳密には異なるのですが，個人的にそこはなろうを語るうえで大して重要な違いではないと思います

*27:実際，掛け算すらも知られてないような異世界で主人公が掛け算を教えて活躍するなろう作品の実例もあります

*28:物工の場合，物性寄りの研究とかなら異世界でもそれなりに活躍できそうな気がしますが，実際どうなんでしょうね

*29:そもそも「なろう読者」でない限りそんな悲観することは普通ないのかも知れませんが……

tener’s diary

てねーるのブログ記事です