大门| 2007年大门|问题17

幂运算是公钥密码术中常用的一种运算。以下哪个选项是计算b所需乘法数的最严格上限 ^N 模m，0≤b、 n≤M （A） O（logn） （B） O(√n） （C） O（北区/北区） （D） O（n） 答复: （A） 说明：

这个问题可以用分而治之的模式来解决

算法：

Binary_exp(b,n)                            // Compute bn mod m

{

    if(n == 0)

        Return 1;

    Else if(n == 1)

        Return b mod m;

    Else

    {

        Half = Binary_exp(b,n/2);

        if(n%2 == 0)                                // n is even

            Return (Half*Half) mod m;

        Else                                    // n is odd

            Return (((Half*Half) mod m)*n) mod m;

}

}          

给出了计算上述算法时间复杂度的递推关系 T（n）=T（n/2）+常数=（log2n）

这个解决方案是由 Pranjul Ahuja . 这个问题的小测验