書記が数学やるだけ#342 繰り返し自乗法，mを法としたk乗根の計算

冪乗の余りを計算するのに，効率よく計算するアルゴリズムが不可欠である。

問題

割る数が小さければ短い周期性から推測できるが，大きいとそれも大変である。そこで，繰り返し自乗法を用いる。

説明

繰り返し自乗法は，指数を2の累乗に分解することで計算を効率化する。

ここで，2の累乗の余りについて計算しておく。ひとつ前の余りを利用して，以下の表を作成することができる。

「mを法としたk乗根の解を求める」問題は，繰り返し自乗法により解くことができる。

解答

これは中学入試の問題で，実際には規則性に気づくかを問われていたか。合同式を考えると，ちょうど2^8で余りが1になるので，これを利用する。

繰り返し自乗法の準備として，2の累乗の余りを求めておく。

指数を2の累乗で分解して，逐次余りを求めることで目当ての余りにたどり着く。

「mを法としたk乗根の解を求める」問題の例，なぜ上手くいくかは手順を辿ればわかる。

なお，Pythonには繰り返し自乗法による累乗計算を行うpow関数が実装されている。競技プログラミングにおける高速化のテクニックとして用いられるそうだ。

pow(x,y)でx^yの値，pow(x,y,z)でx^yをzで割った余りの値を返す。

>>pow(7,327)

2223612386895518058260844904754870512330526141313192828467451057288631607010887701537127826455054123887591219817828214033864422437370927546471171195869627712246327776729283233680630367758293260008306423955403182462660444821909776232862666752849867105859105032584937995509879543

>>> pow(7,327,853)

286

本記事のもくじはこちら：