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
アルゴリズムの経過| 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 |
nbFPower[a_, n_, m_] := Module[{y = 1, arr = Bin[n], i},
For[i = Length[arr] - 1, i >= 0, i--,
y = Mod[y^2, m];
If[Part[arr, Length[arr] - i] == 1, y = Mod[y*a, m]];
];
Return[y];
]
尚、Mathematicaにはもともと PowerMod という同様の関数がある