繰り返し二乗法

目的

$a^n \mod m$を$O(\log m)$で求めます。

計算量

$O(\log m)$

使い方

integer(kind=8) function pow(a,pwr)
$a^{pwr} \mod m$をreturnします。

ソースコード

integer(kind=8) function pow(a,pwr)
	implicit none
	integer(kind=8),value::a,pwr
	pow=1
	do while(pwr>0)
		if(mod(pwr,2)==1)pow=mod(pow*a,m)
		a=mod(a*a,m)
		pwr=pwr/2
	end do
end function