繰り返し自乗法を実装する - Ex16.2(b)(c)

今回も『はじめての数論』の演習問題をやっていきます．

作者:Joseph H. Silverman
丸善出版

今回やるのは Ex16.2(b)(c)です．

問題文

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.

(i) $2^ {1000} \mod 2379$

(ii) $567^ {1234} \mod 4321$

(iii) $47^ {258008} \mod 1315171$

（引用元: Silverman『A Friendly Introduction to Number Theory』p.116）

問b の回答

前回の記事では問aを解きました．

それは，疑似コードで示した上記のアルゴリズムが繰り返し自乗法になっていて，$a^ k \mod m$ を計算することを示せというものでした．

今回やる問題では，それを計算機の上で実装せよといっています．

Juliaで書くことにします．

# 繰り返し自乗法
## 入力
## a^k mod m を求める
a = 7
m = 307
k = 306
## 手続き
b = 1
while k >= 1
    if k % 2 == 1
        b = (a * b) % m
    end
    a = (a*a) % m
    k = div(k,2)
end
print(b)

以上です．

特にコメントすべきこともありません．

問c の回答

上記のコードでJuliaさんをお呼びして計算してもらいました．

(i) $2^ {1000} = 562 \mod 2379$

(ii) $567^ {1324} = 3214 \mod 4321$

(iii) $47^ {258008} = 1296608 \mod 1315171$

全部一瞬で終わりました．あたまの悪いアルゴリズムと比較した方が分かりやすくて良かったかもしれません．

感想とまとめ

Juliaってなんでendが必要なんでしょうか．Pythonでは要らなかったのに．

何か理由があるんだと思うんですけど，想像もつかないです．

それはそうとして「プログラムを書きました！」で終わりというのはつまらないですね．

今後は計算機を扱うにしても，もう少し複合的な問題をやっていきたいです．

パンの木を植えて

主として数学の話をするブログ

繰り返し自乗法を実装する - Ex16.2(b)(c)

問題文

問b の回答

問c の回答

感想とまとめ