模幂运算是计算一个整数的幂对某个正整数取模的结果。给定底数 、非负指数 和模数 ,它求出满足下列条件的唯一整数 :
它在计算上的核心优势是可以随时将中间结果对 取模,从而避免构造可能极其庞大的整数 。模幂运算是数论、计算数学和公钥密码学中的一项基本运算。
定义与基本性质
在模算术中,相差 的整数倍的整数属于同一个剩余类。模幂运算的结果仅取决于底数所属的剩余类:对于任意非负整数 ,都有
通常的指数运算法则仍然成立:
特别地,恒等式
使得每次乘法之后都可以进行取模。
对于 ,模幂算法采用空积约定 ,即使 也不例外。因此,返回的余数为 。若 ,所有结果均为 。模数不能为零。
例如,
因此,
无需构造有 85 位数字的整数 。
二进制幂算法
标准的高效算法是二进制幂算法,也称为平方求幂法或平方乘法。它利用以下恒等式:
该算法逐位处理 的二进制表示,所需模乘次数仅与 的二进制位数成正比,而不必进行大约 次乘法。
从右向左处理的版本如下:
模幂(a, e, m):
要求 e >= 0 且 m >= 1
结果 = 1 mod m
底数 = a mod m
当 e > 0 时:
如果 e 为奇数:
结果 = (结果 * 底数) mod m
e = 向下取整(e / 2)
底数 = (底数 * 底数) mod m
返回 结果
每次迭代开始时,循环都保持以下不变式:
其中, 和 是最初的输入,公式中的 result 和 base 分别对应伪代码中的“结果”和“底数”。当剩余指数变为零时,这个不变式就表明“结果”是所求的余数。对迭代次数运用数学归纳法,即可给出严格的正确性证明。
从左向右处理的版本则从最高位到最低位扫描指数的二进制位。从 开始,每处理一位就将 平方;若该位为 ,再乘以 。
计算示例
要计算 ,先写出
连续平方可得
将非零二进制位所对应的幂相乘,得到
计算复杂度
对于 ,令
为指数的二进制位数。用大O记号表示,二进制幂算法需要 次模乘。若实现时用最高位对应的幂初始化累积值,则可以只进行 次平方,并为其余每个非零指数位各进行一次额外乘法。
这一运算次数并不等同于位复杂度。设 为 的二进制位数。取模后的余数最多占 位,而两个余数相乘后尚未取模的积可能占约 位。采用普通竖式乘法和常规的基于除法的取模方法时,每次模乘需要 次位运算,因此,不计输入的初始取模,整体复杂度上界为
更一般地,若 表示两个 位余数相乘并取模的开销,则运行时间为
更快的乘法和取模方法能够降低这一开销。
基本算法只需存储常数个大整数,但也需要读取指数并使用临时工作空间。基于窗口的变体则以额外存储和预计算为代价,减少乘法次数。
更快的实现方法
加法链与窗口方法
的一条加法链是一个以 开始、以 结束的数列,其中每个新项都是前面两项之和。每一项都对应一个幂,该幂可以通过将先前算出的两个幂相乘得到。
二进制幂算法给出了一条这样的链,但它不一定最短。例如,加法链
只需五次乘法即可算出 ,而直接使用二进制方法构造的链需要六次。
固定窗口法和滑动窗口法将指数的若干二进制位合在一起处理,并预先计算底数的某些幂。对于较大的指数,这些方法可以减少乘法次数,尤其适合预计算结果能够重复利用的情况。
取模方法
蒙哥马利乘法通过在一种变换后的表示形式中进行运算,取代反复除以模数的操作。它要求辅助基数与 互素。若基数是二的幂,就意味着 必须是奇数。
巴雷特约减则利用预先计算的模数倒数近似值来加速取模。它不要求模数为奇数。
当大量乘法使用同一个模数时,这两种技术尤其有用,而模幂运算正是这样的情形。
指数约简与周期性
将底数对 取模总是有效的,但对指数进行取模约简则需要额外条件。
其中, 表示与 互素的剩余类个数。因此,对于非负的 ,
更确切地说,可逆剩余类的各次幂以其乘法阶为周期重复:乘法阶就是使 成立的最小正整数 。这是群论中元素的阶的一个具体例子。
若 与 不互素,将指数对 取模可能会出错。例如,
但将指数对 取模,会错误地得到
对于任意固定的底数和模数,其非负整数次幂在取模后形成的序列最终都会呈现周期性,但不一定从指数为零时就开始周期重复。
若模数被分解为两两互素的因子,可以分别以这些因子为模计算幂,再利用中国剩余定理合并结果。
负指数
以 为模时,只有底数存在乘法逆元,负指数幂才有定义。逆元存在的充要条件是
将逆元记为 ,则对于正整数 ,定义
逆元可以使用扩展欧几里得算法求出。例如,
因为 ,所以
若逆元不存在,通常意义下具有单一确定值的负指数模幂便没有定义。
应用与安全性
模幂运算在多种计算任务中都居于核心地位:
- 公钥密码学。 RSA密码系统使用以大素数之积为模的幂运算。乘法群中的迪菲–赫尔曼密钥交换则选取一个合适的素数作为模数,计算共同底数的幂。
- 素性测试。 米勒–拉宾测试等方法通过检查模幂是否具有素数模数应有的性质,来检验素性。
- 计算数论。 整数分解方法、阶的计算以及有限域中的计算都会用到模幂。
- 离散对数。 计算 很高效,但在恰当选取的群中,从给定的群元素反求 可能十分困难。这种差异是基于离散对数的密码系统的基础。
当指数需要保密时,数学上正确的实现并不一定安全。普通的平方乘法会根据指数位的不同执行不同操作;运行时间、功耗、电磁辐射或内存访问模式都可能泄露这些位的信息。
因此,密码学实现会采用经过精心设计的运算流程、常数时间的查表选择,并在适当情况下使用盲化技术。仅仅固定乘法次数,并不能保证抵抗信息泄露:还必须考虑底层的乘法、取模和内存操作。
整数的表示方式同样重要。在固定位宽的机器算术中,乘积可能在取模之前就已溢出。实现时可以使用足够宽的中间值、多精度算术,或能够避免溢出的模乘过程。先用浮点运算近似计算一个大整数幂,再求其余数,不能替代精确的模幂运算。
代数推广
平方求幂法依赖的是结合律和单位元,而非整数乘法本身。因此,同一种方法也适用于环(数学)中的元素,包括矩阵,以及以另一个多项式为模进行约简的多项式。
对于元素均对 取模的矩阵,二进制幂算法能够高效计算 。这可用于涉及递推关系和离散变换反复作用的计算。与标量不同,矩阵之间的乘法不一定满足交换律,但同一个固定矩阵的各次幂仍满足算法所需的恒等式。