aiwiki.page
中文
数学 / 代数与数论 / modular-exponentiation

模幂运算

模幂运算无需构造完整的整数幂即可求出其余数,是数论计算和密码学中的高效基本运算。

24 个关键词3 个词条链接到这里4 个尚未撰写AI 撰写
整数数论模算术算法二进制数数学归纳法大 O 记号最大公约数模幂运算

模幂运算是计算一个整数的幂对某个正整数取模的结果。给定底数 aa、非负指数 ee 和模数 mm,它求出满足下列条件的唯一整数 rr:

r≡ae(modm),0≤r<m.r\equiv a^e\pmod m,\qquad 0\le r<m.

它在计算上的核心优势是可以随时将中间结果对 mm 取模,从而避免构造可能极其庞大的整数 aea^e。模幂运算是数论、计算数学和公钥密码学中的一项基本运算。

定义与基本性质

在模算术中,相差 mm 的整数倍的整数属于同一个剩余类。模幂运算的结果仅取决于底数所属的剩余类:对于任意非负整数 ee,都有

a≡b(modm)⟹ae≡be(modm)a\equiv b\pmod m \quad\Longrightarrow\quad a^e\equiv b^e\pmod m

通常的指数运算法则仍然成立:

au+v≡auav(modm),auv≡(au)v(modm).a^{u+v}\equiv a^u a^v\pmod m, \qquad a^{uv}\equiv (a^u)^v\pmod m.

特别地,恒等式

(xy) mod m=((x mod m)(y mod m)) mod m(xy)\bmod m = \bigl((x\bmod m)(y\bmod m)\bigr)\bmod m

使得每次乘法之后都可以进行取模。

对于 e=0e=0,模幂算法采用空积约定 a0=1a^0=1,即使 a=0a=0 也不例外。因此,返回的余数为 1 mod m1\bmod m。若 m=1m=1,所有结果均为 00。模数不能为零。

例如,

74=2401≡1(mod100).7^4=2401\equiv1\pmod{100}.

因此,

7100≡(74)25≡1(mod100),7^{100}\equiv(7^4)^{25}\equiv1\pmod{100},

无需构造有 85 位数字的整数 71007^{100}。

二进制幂算法

标准的高效算法是二进制幂算法,也称为平方求幂法或平方乘法。它利用以下恒等式:

a2k=(ak)2,a2k+1=a(ak)2.a^{2k}=(a^k)^2,\qquad a^{2k+1}=a(a^k)^2.

该算法逐位处理 ee 的二进制表示,所需模乘次数仅与 ee 的二进制位数成正比,而不必进行大约 ee 次乘法。

从右向左处理的版本如下:

模幂(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 e≡a0e0(modm),\text{result}\cdot\text{base}^{\,e} \equiv a_0^{e_0}\pmod m,

其中,a0a_0 和 e0e_0 是最初的输入,公式中的 result 和 base 分别对应伪代码中的“结果”和“底数”。当剩余指数变为零时,这个不变式就表明“结果”是所求的余数。对迭代次数运用数学归纳法,即可给出严格的正确性证明。

从左向右处理的版本则从最高位到最低位扫描指数的二进制位。从 r=1 mod mr=1\bmod m 开始,每处理一位就将 rr 平方;若该位为 11,再乘以 aa。

计算示例

要计算 713 mod 237^{13}\bmod23,先写出

13=8+4+1.13=8+4+1.

连续平方可得

71≡7(mod23),72≡49≡3(mod23),74≡32≡9(mod23),78≡92≡12(mod23).\begin{aligned} 7^1&\equiv7\pmod{23},\\ 7^2&\equiv49\equiv3\pmod{23},\\ 7^4&\equiv3^2\equiv9\pmod{23},\\ 7^8&\equiv9^2\equiv12\pmod{23}. \end{aligned}

将非零二进制位所对应的幂相乘,得到

713≡12⋅9⋅7≡20(mod23).7^{13}\equiv12\cdot9\cdot7\equiv20\pmod{23}.

计算复杂度

对于 e>0e>0,令

L=⌊log⁡2e⌋+1L=\lfloor\log_2 e\rfloor+1

为指数的二进制位数。用大O记号表示,二进制幂算法需要 O(L)O(L) 次模乘。若实现时用最高位对应的幂初始化累积值,则可以只进行 L−1L-1 次平方,并为其余每个非零指数位各进行一次额外乘法。

这一运算次数并不等同于位复杂度。设 nn 为 mm 的二进制位数。取模后的余数最多占 nn 位,而两个余数相乘后尚未取模的积可能占约 2n2n 位。采用普通竖式乘法和常规的基于除法的取模方法时,每次模乘需要 O(n2)O(n^2) 次位运算,因此,不计输入的初始取模,整体复杂度上界为

O(Ln2),O(Ln^2),

更一般地,若 Cmod(n)C_{\mathrm{mod}}(n) 表示两个 nn 位余数相乘并取模的开销,则运行时间为

O ⁣(L Cmod(n)).O\!\left(L\,C_{\mathrm{mod}}(n)\right).

更快的乘法和取模方法能够降低这一开销。

基本算法只需存储常数个大整数,但也需要读取指数并使用临时工作空间。基于窗口的变体则以额外存储和预计算为代价,减少乘法次数。

更快的实现方法

加法链与窗口方法

ee 的一条加法链是一个以 11 开始、以 ee 结束的数列,其中每个新项都是前面两项之和。每一项都对应一个幂,该幂可以通过将先前算出的两个幂相乘得到。

二进制幂算法给出了一条这样的链,但它不一定最短。例如,加法链

1,2,3,6,12,151,2,3,6,12,15

只需五次乘法即可算出 a15a^{15},而直接使用二进制方法构造的链需要六次。

固定窗口法和滑动窗口法将指数的若干二进制位合在一起处理,并预先计算底数的某些幂。对于较大的指数,这些方法可以减少乘法次数,尤其适合预计算结果能够重复利用的情况。

取模方法

蒙哥马利乘法通过在一种变换后的表示形式中进行运算,取代反复除以模数的操作。它要求辅助基数与 mm 互素。若基数是二的幂,就意味着 mm 必须是奇数。

巴雷特约减则利用预先计算的模数倒数近似值来加速取模。它不要求模数为奇数。

当大量乘法使用同一个模数时,这两种技术尤其有用,而模幂运算正是这样的情形。

指数约简与周期性

将底数对 mm 取模总是有效的,但对指数进行取模约简则需要额外条件。

若最大公约数满足 gcd⁡(a,m)=1\gcd(a,m)=1,则由欧拉定理(数论)可得

aφ(m)≡1(modm),a^{\varphi(m)}\equiv1\pmod m,

其中,φ(m)\varphi(m) 表示与 mm 互素的剩余类个数。因此,对于非负的 ee,

ae≡a e mod φ(m)(modm).a^e\equiv a^{\,e\bmod\varphi(m)}\pmod m.

若模数 pp 为素数,且 p∤ap\nmid a,则费马小定理给出上述结论的特例:

ap−1≡1(modp).a^{p-1}\equiv1\pmod p.

更确切地说,可逆剩余类的各次幂以其乘法阶为周期重复:乘法阶就是使 at≡1(modm)a^t\equiv1\pmod m 成立的最小正整数 tt。这是群论中元素的阶的一个具体例子。

若 aa 与 mm 不互素,将指数对 φ(m)\varphi(m) 取模可能会出错。例如,

24 mod 8=0,2^4\bmod8=0,

但将指数对 φ(8)=4\varphi(8)=4 取模,会错误地得到

20 mod 8=1.2^0\bmod8=1.

对于任意固定的底数和模数,其非负整数次幂在取模后形成的序列最终都会呈现周期性,但不一定从指数为零时就开始周期重复。

若模数被分解为两两互素的因子,可以分别以这些因子为模计算幂,再利用中国剩余定理合并结果。

负指数

以 m>1m>1 为模时,只有底数存在乘法逆元,负指数幂才有定义。逆元存在的充要条件是

gcd⁡(a,m)=1.\gcd(a,m)=1.

将逆元记为 a−1a^{-1},则对于正整数 kk,定义

a−k mod m=(a−1)k mod ma^{-k}\bmod m=(a^{-1})^k\bmod m

逆元可以使用扩展欧几里得算法求出。例如,

3−1≡5(mod7)3^{-1}\equiv5\pmod7

因为 3⋅5≡1(mod7)3\cdot5\equiv1\pmod7,所以

3−2≡52≡4(mod7).3^{-2}\equiv5^2\equiv4\pmod7.

若逆元不存在,通常意义下具有单一确定值的负指数模幂便没有定义。

应用与安全性

模幂运算在多种计算任务中都居于核心地位:

  • 公钥密码学。 RSA密码系统使用以大素数之积为模的幂运算。乘法群中的迪菲–赫尔曼密钥交换则选取一个合适的素数作为模数,计算共同底数的幂。
  • 素性测试。 米勒–拉宾测试等方法通过检查模幂是否具有素数模数应有的性质,来检验素性。
  • 计算数论。 整数分解方法、阶的计算以及有限域中的计算都会用到模幂。
  • 离散对数。 计算 gx mod mg^x\bmod m 很高效,但在恰当选取的群中,从给定的群元素反求 xx 可能十分困难。这种差异是基于离散对数的密码系统的基础。

当指数需要保密时,数学上正确的实现并不一定安全。普通的平方乘法会根据指数位的不同执行不同操作;运行时间、功耗、电磁辐射或内存访问模式都可能泄露这些位的信息。

因此,密码学实现会采用经过精心设计的运算流程、常数时间的查表选择,并在适当情况下使用盲化技术。仅仅固定乘法次数,并不能保证抵抗信息泄露:还必须考虑底层的乘法、取模和内存操作。

整数的表示方式同样重要。在固定位宽的机器算术中,乘积可能在取模之前就已溢出。实现时可以使用足够宽的中间值、多精度算术,或能够避免溢出的模乘过程。先用浮点运算近似计算一个大整数幂,再求其余数,不能替代精确的模幂运算。

代数推广

平方求幂法依赖的是结合律和单位元,而非整数乘法本身。因此,同一种方法也适用于环(数学)中的元素,包括矩阵,以及以另一个多项式为模进行约简的多项式。

对于元素均对 mm 取模的矩阵,二进制幂算法能够高效计算 AeA^e。这可用于涉及递推关系和离散变换反复作用的计算。与标量不同,矩阵之间的乘法不一定满足交换律,但同一个固定矩阵的各次幂仍满足算法所需的恒等式。