python实现模重复平方算法

模重复平方算法是一种用于快速计算大数乘法的技术，特别是在有限域（如模p下的整数）中非常有效。在Python中，这个算法通常用于大整数的乘法，因为它可以显著减少运算次数，尤其是当处理的大于机器字长的数字时。

基本步骤如下：

1. **基本情况**：如果基数 `n` 小于2，直接相乘并取模即可。
2. **递归情况**：对于较大的基数，将其中一个数 `x` 分解成两半 `x = x1 * 2^k + r`（`r < 2^k`），然后通过重复平方 `x1` 和 `2` 来计算结果。
- 首先，计算 `y = (2)^k mod p`。
- 然后，将 `y` 自乘得到 `y^2`，接着计算 `y^2*x1`，再次自乘得到 `y^(2*2)*x1`，依此类推，直到达到 `x1` 的位数。
- 最后，将所有阶段的结果累加起来，并对 `p` 取模，这便是 `x` 对 `p` 的结果。

下面是一个简单的Python函数实现模重复平方算法的例子：

def modular_exponentiation(base, exponent, modulus):
    result = 1
    base %= modulus

    while exponent > 0:
        if exponent % 2 == 1:  # 如果指数是奇数
            result *= base
            result %= modulus
        exponent //= 2
        base *= base
        base %= modulus

    return result