大数模幂运算快速算法概要

1、有朋友问我的博文素性测试中的Miller-Rabin算法的大数模幕运算快速算法怎么 理解,由于在素性测试中没有讲解算法原理，所以在此单独一个篇文章详细讲这个算法。 这是一个在密码学中比较重要的算法，在我的素性测试一文则是用于实现费马小定理。首先我们先把问题简化一下，看看如何快速求aAb.先看看我们熟知的两个数学公式：aA(2c = (aAcA2;aA(2c+1 = a*(aAcA2;我们就利用这两个数学公式来解决这个问题，比如a=3,b=13时,我们把b写成二进制的 形式13(10=1101 (2,我们从低位到高位运算，每运算一位可以将b右移一位,上面的例子可以 转化成3A13 = 3A1 *

2、 3A4 * 3A8,结合上面的两个数学公式我们可以 写出如下的代码：代码清单：javaview pla in copySt wid »! rb( rl«<( J工mt a >)uni b = J);&_ t.« pOH(i*j*te)js) it Aprifrt ln( B»s.19.MHfpruviitfl- st»tir rt pcu( i M a> int to)("unt rcfiuilt JjuhllW> B)|if(Cte& 1 乂沔 D11 ： Jreakull *- ：a *I

3、B.b >> Jj a20.21. return result22.a如上面的叙述叙述中可以看出快速POW算法的时间复杂度取决于b的二进制位数，而传统的一位一位累乘的pow算法的时间复杂度取决于b的大小，例如上述例子中, 两种算法的运算次数分别为4次，和13次。随着b的增大，效率上的差距是显然的。下面进入我们的主题一大数模幕运算快速算法(aAb % m要计算这个，我们首先还要知道一个数学公式：aAb % m = (.(a % m * a % m .* a % m 其中 a%m 有 b 个下面我还用上面b=13的例子，利用这个公式来证明下aA13 % m = (八 8 % m * (

4、八 4 % m * (八 1 % m证明:由 aAb % m = (.(a%m* a %m.* a % m 其中 a%m 有 b 个得aA8 % m =(.(a%m* a% m.*a%m其中a%m 有8 个aA4 % m =(.(a%m* a% m.*a%m其中a%m 有4 个aA1 % m =(.(a%m* a% m.*a%m其中a%m 有 1 个所以(aA8 % m * (aA4 % m * (八 1 % m = (.(a %m*a%m.*a%m 其中 a%m 有 13 j=aA13 % m ;证毕。由上面我们证明的公式和第一个 pow的例子，容易写出代码如下：代码清单：javaview

5、pla in copy20.23 «return： result j3. int result = Jjwhile (b > ©) 5,if <(bi J) =1)籽.result =. (result * a)j7.S.ba (a * a) % :9bb » ijw. j (. return result % ;解释：当b=1101(2时，从第1位开始result累乘声=%m加上循环可以看成表达式匕17?2 %m.因为（a%mA2 % m = aA2 % m所以我们可以把aA13%m看成（aA1 % m ,（aA4 % m，（ 八8 % m的累乘，最后对m取模。但累乘很容易造成溢出，所以我们可以把代码改成如下形式： 代码清单:javaview pla in copyJ Lint resujt L2 Jj4. whil« (b > 0) 轧if(b 盘 J“1>6.result > (result b »= Ijj j,return result %解释,b=1