快速指数运算法一平方再乘法 快速指数运算法一平方再乘法 Square and multiply 当x为n位时即X=(Xn1,Xn2,,X1,X0 (g)=gx=(.(1·gxn-)2·gxn-2)2·gxn-3.)2·g 此算法共需要n-1次平方及W(x)-1次乘法,平均而言 W(Xx)=n/2,x在二进制表示时有n/2个”0”及n/2个”1”。 因此,当x为n位时,平均需要1.5n-2个乘法(平方算 次乘)。 注:如果x为k进制数,即变为k次方再乘法,效率更高? (需要提前计算并存储g2,g3,,gk-) 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 23/81mfy@ustc.edu.cn 现代密码学理论与实践 23/81  快速指数运算法—平方再乘法(Square and multiply) 当x为n位时即x=(xn-1 , xn-2 ,…,x1 , x0 ) Ex(g)=gx=(…(1•gxn-1) 2•gxn-2) 2•gxn-3…)2•gx0  此算法共需要n-1次平方及w(x)-1次乘法, 平均而言 w(x)=n/2, x在二进制表示时有n/2个”0”及n/2个”1”。 因此，当x为n位时, 平均需要1.5n-2个乘法(平方算一 次乘)。  注：如果x为k进制数，即变为k次方再乘法，效率更高？ (需要提前计算并存储g2,g3,…,gk-1)