模指數運算的三個方法

運算型如b^n mod m的演算法 方法一： 先將n表示成二進位 <br />procedure base 2 expansion(n:positive integer)<br />q:=n<br />k:=0<br />while q!=0<br />begin<br /> a[k]:=q mod 2<br /> q:=q/2<br /> k:=k+1<br />end<br />{the base 2 expansion of n is (a[k-1]...a[1]a[0])binary}<br /> 接著使用同餘性質以非常不直觀的方式寫成： <br />procedure modular exponentiation(b:integer,n=(a[k-1]a[k-2]...a[1]a[0])binary,m:positive integers)<br />x:=1<br />power:=b mod m<br />for i:=0 to k-1<br />begin<br /> if a[i]=1 then x:=(x*power) mod m<br /> power:=(power^2) mod m<br />end<br />{x equals b^n mod m}<br /> 方法二： 使用直觀的遞迴演算 利用b^n mod m=(b*(b^(n-1) mod m)) mod m 及初始條件b^0 mod m=1 就可簡單地作成exp_mod_rec(int,int,int); 方法三： 利用n的奇偶性的遞迴運算 <br />procedure mpower(b,n,m:integers)<br />if n=0 then<br /> mpower(b,n,m)=1<br />else if n is even then<br /> mpower(b,n,m)=mpower(b,n/2,m)^2 mod m<br />else<br /> mpower(b,n,m)=(mpower(b,n/2,m)^2 mod m * b mod m) mod m<br />{mpower(b,n,m)=b^n mod m}<br /> 個人是認為 1<=b<m 似乎不需要這個限制。 目前最大的瓶頸是複雜度的求法...... 程式實作如下