expmod - mrsekut-p

expmod

アルゴリズムと具体例

$ a^x\pmod nを求めたい

アルゴリズム

入力: $ a,x,n

出力: $ a^x

$ xを2進数表示$ (x_{k-1},x_{k-2},\cdots,x_0)_2にする

添字が降順なことに注意

$ y=1とおき、$ i=(k-1)\rightarrow0まで以下を繰り返す

step1: $ y:=y^2\pmod n

step2: $ x_i=1なら$ y:=y\times a\pmod n

最後に$ yを出力

$ x=19を考える

2進数表示は$ (10011)_2

なので$ k=4

table:アルゴリズムの経過

i y x_i yを更新する

4 1^2 1 y := 1×a = a

3 a^2 0 なにもしない

2 (a^2)^2 0 なにもしない

1 ((a^2)^2)^2 1 y := ((a^2)^2)^2 * a

0 (((a^2)^2)^2 * a)^2 1 y := (((a^2)^2)^2 * a)^2 * a

上のアルゴリズムと全く同じものをMathematicaで書いた

code:nb

FPowera_, n_, m_ := Module[{y = 1, arr = Binn, i},

For[i = Lengtharr - 1, i >= 0, i--,

y = Mody^2, m;

If[Part[arr, Lengtharr - i] == 1, y = Mody*a, m];

];

Returny;

]

尚、MathematicaにはもともとPowerModという同様の関数がある