今日すること

ruby でプログラミングを行ない、 正の数$a,b,m$ と (大きな)数 $n$ に対して、 $a^n$ を $m$ で割ったあまりを計算する関数 $f(a,n,m)$ を作る。 実際に実行してみてプログラムとその結果を verbatim を用いて TeX に取り込んで提出せよ。

◎アイディアその1. $f(a,n,m)=a^n \mod m$ を求めるのに、わざと少し余分な $c$ も考えて、 $g(c,a,n,m)=c a^n \mod m$ を作る。( $f(a,n,m)=g(1,a,n,m)$ である。)

◎アイディアその2. べき指数 $n$ を $2$ でわって、 $n = 2 q + r$ と書くと

$$c a^n \mod m = (c \cdot a^r) (a^2)^{q} \mod m$$