今回も『はじめての数論』の演習問題をやっていきます．
今回やるのは演習問題 16.2 です．
問題文
原著の電子書籍を入手したので，今回から問題文が英語です．
The method of successive squaring described in the text allows you to compute $a^ k \mod m$ quite efficiently, but it does involve creating a table of powers of a modulo $m$.
(a) Show that the following algorithm will also compute the value of $a^ k \mod m$. It is a more efficient way to do successive squaring, well-suited for implementation on a computer.
(1) Set $b=1$
(2) Loop While $k \geq 1$
(3) If $k$ is odd, set $b=a \cdot b \mod m$
(4) Set $a=a^ 2 \mod m$.
(5) Set $k = k/2$ (round down if $k$ is odd)
(6) End of Loop
(7) Return the value of $b$ (which equals $a^ k \mod m$)
(b) Implement the above algorithm on a computer using the computer language of your choice.
(c) Use your program to compute the following quantities:
(i) $2^ {1000} \mod 2379$
(ii) $567^ {1234} \mod 4321$
(iii) $47^ {258008} \mod 1315171$
（引用元: Silverman『A Friendly Introduction to Number Theory』p.116）
はてなブログに英文を書くとあまりきれいに表示されないので，今回限りでやめるかもしれません．
問題の背景
問題文のなかに successive squaring と書いてあるのが読めると思いますが，これは日本語で繰り返し自乗法といいます．
ある整数 $m$ を法として数 $a$ のベキ $a^ k$ を計算したいものとします．このとき $a^ k$ を計算してから，それを $m$ で割ってあまりを求めていたのでは，大きな数を扱わないといけないのでメモリを食いますし，大きな数の掛け算は大変なので時間もかかります．
$a$ を一回乗ずるごとにあまりを求めれば，$m ^2$ より大きな数は扱わなくて済むのでかなりマシになりますが，それでも掛ける操作を $k$ 回繰り返す必要があります．
よりうまい方法はないでしょうか？というのが問題意識としてあります．
そこで登場するのが繰り返し自乗法です．
具体例を見るのが早いです．
たとえば，本に載っている例ですけど $7^{327} \mod 853$ を計算することを例としてみてみましょう．
まず指数である $k= 327$ を２進数に直します．見づらくなるので10進数のまま表記しますが，$327 = 256 + 64 + 4 + 2 + 1$ です．
次に自乗を繰り返すことで， $7 \mod 853$ のベキ乗の表を作成します．
$7^ 2 = 49$
$7^ 4 = 49^ 2 = 695$
$7^ 8 = 695^ 2 = 227$
以下省略しますが，$7^ {256}$ まで計算します．ここでポイントは，$7^ 3$ とかは計算しないことです．なぜなら，$7^ 3 = 7 \cdot 7^ 2$ というように後で計算できるからです．計算するのは指数が２のベキになっているものだけ．だから繰り返し自乗するだけで十分なわけです．
あとは $7^ {256} \cdot 7^ {64} \cdot 7^ 4 \cdot 7^ 2 \cdot 7$ を計算して終わりです．答えは $286 \mod 853$ です．
この方法なら掛け算は $O(\log k)$ 回程度ですみます．
回答 - 問a
上記の繰り返し自乗法のアルゴリズムでは，$a ^k \mod m$ の表を作成していました．
表を作成してその値を記憶するには $O(\log k)$ くらいのメモリを食いますので，なるべく表を作らずに計算したいです．
そこで，問題文にあるようなアルゴリズムを考えたという経緯があるようです．
さてそれでは，与えられたアルゴリズムの分析をしていきましょう．
与えられたアルゴリズムは，疑似コードで書くとこんな感じです．
よくわかりませんね．なんとなく繰り返し自乗してそうな気もするんですけど．
とりあえず $k$ が奇数かどうかで分岐しているのが気になるので，この部分だけ取り出したコードを考えてみます．
これはおそらく $k$ を二進展開するプロセスから来ているのだと思われます．そういうわけなので一旦２進展開のアルゴリズムを書いてみて照合しましょう．
これが２進展開のアルゴリズムです．そっくりですね．
たとえば $k=6$ を放り込むと，A = [0 1 1] が返ってきます．
通常の２進数と順番が逆であることだけ注意してください．
この２進展開アルゴリズムに細工をして，繰り返し自乗法を自分で書いてみましょう．
$A$ が $k$ の２進展開を下の桁から順に計算しているんですから，それに合わせて $a$ を自乗して掛けてを繰り返せばよいはずです．
このようにしてコードを書いてみると，$A$ の情報を保持する必要はまったくないことがわかります．そこで $A$ についてどうこう書いている箇所をすべて削除すると，元のアルゴリズムに一致しています．
したがって当該アルゴリズムは，繰り返し自乗法と同じものだったことがわかります．
感想とまとめ
疑似コードにアルゴリズム本体の動きとは関係がない変数を追加することで，却って可読性が上がるというのはおもしろいですね．
次回は Julia を呼んでこのコードを実際に動かす予定です．
繰り返し自乗法がなぜ重要かですが，逆の「根を求める」操作が難しいことが暗号理論で重要だから…というのがあります．Silvermanによるこの本はかなり良くできていて，暗号理論についての詳しい説明があるんです．
暗号理論についての説明はこのブログでもやるつもりをしております．
最近，代数幾何どころか初等整数論ばっかりやってて読んでるひとには「何をしてるんだこいつは」と思われてそうです．
でもシルヴァーマンのこの本は学部の時から読もう読もうと思って放置してたんで，ゆっくり読む時間がとれてよかったです．（今後は時間がとれるかどうか不明ですが）
