高速冪乗法 - mrsekut-p

高速冪乗法

一般に$ a^{2^k}の計算は

普通に計算すれば$ 2^k-1回

高速冪乗法を使えば$ k回で済む

例えば$ 3^{32}を素朴に計算すると

$ 3\times3\times\cdots\times3というふうに31回計算する必要があるが、

$ ((((3^2)^2)^2)^2)^2と計算すれば5回ですむ

$ a^xを求める手順

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

つまり$ x=x_{0}+2 x_{1}+2^{2} x_{2}+\cdots+2^{k-1} x_{k-1}

なので$ a^xは以下のように書ける

$ a^{x}=a^{x_{0}+2 x_{1}+2^{2} x_{2}+\cdots+2^{k-1} x_{k-1}}=a^{x_{0}}\times\left(a^{2}\right)^{x_{1}} \times\left(a^{2^{2}}\right)^{x_{2}} \times \cdots \times\left(a^{2^{k-1}}\right)^{x_{k-1}}

最初の等号は$ xを上の「つまり」の式に変えているだけ

本質は最右辺

$ a^{2^k}の使い回しだけで計算できている

このページを参考にしても書いてみた

code:nb

powera_, 0 := 1

power[a_, n_ /; EvenQn] := power[a*a, (Quotientn, 2)]

power[a_, n_ /; OddQn] := a*powera, (n - 1)

FPowera_, n_, m_ := Mod[powera, n, m]