利用逐次平方法快速求幂

• yuanli04525 发布于
• 1472 收藏

利用逐次平方法可以快速求幂，这里不局限于数的幂，但以数的幂来举例说明。 要求ak，如果直接用a连乘k次，复杂度比较大。如果把k写成如下形式： k = u0 + 2u1 + 22u2 + … + 2rur, ui = 0 或 1. 然后制作模a的幂次表： a1 = A0, a2 = (a1)2 = A02 = A1, … a2r = (a2r-1)2 = Ar-12 = Ar. ...