整数算法可以处理极其巨大的数值,却不必遍历所有更小的整数。这是因为余数保留了我们所需的整除信息,而一个二进制位可以描述一大段重复的乘法。关键的技能是辨明每次压缩之后究竟保留了什么。我们将对欧几里得(Euclid)算法使用公因数不变量,对模幂运算使用乘积不变量,然后考察它们的紧凑描述实际需要多少运算量。
动机
设某个程序必须求解 17x≡1(mod43)。在这里逐一检验全部四十三个剩余类可以得到答案,但这既无法解释为什么解存在,也无法处理数百位的模数。最大公约数的计算则两者兼顾:它的余数揭示逆元是否存在,而它的代入过程把逆元作为一个证书给出,只需一次乘法和一次取余便可检验。
同样地,若通过把 a 恰好乘 e 次来计算 ae,就忽略了 e 是如何被给出的。一个有 k 个二进制位的指数可能接近 2k。于是长度为 e 的循环相对于输入中这一部分的长度而言是指数级的。重复平方法逐位处理指数的各个数字,从而只需关于 k 为线性次数的模乘法,就能得到同一个数学上的幂。
这些都是精确的整数算法。它们的证书表达的是等式与整除关系,不含任何数值容差。这使它们与下一章的近似保证形成有益的对照。精确并不意味着算术是免费的:即使我们把两个长整数的乘法写成一个乘积,它也涉及许多位运算。
定义
对于整数 d,a,记号 d∣a 表示存在整数 c 使得 a=dc。对于不全为零的非负整数 a,b,它们的最大公约数 gcd(a,b) 是同时整除两者的最大正整数。对 a>0,我们约定 gcd(a,0)=a。对于任意符号的整数,应先取绝对值,再应用非负整数的算法。
对于整数 a 与 b>0,带余除法给出唯一的整数 q,r,使得 a=qb+r 且 0≤r<b。欧几里得算法从一个非负数对 (a,b) 出发,当 b>0 时反复把它替换为 (b,amodb)。当第二个坐标变为零时,其输出为第一个坐标。
固定模数 m≥2。同余式 a≡b(modm) 表示 m∣(a−b)。每个剩余类可以由 0,1,…,m−1 之一作为规范代表。a 的模逆元是满足 au≡1(modm) 的整数 u。当逆元存在时,唯一的是 u 所在的剩余类;整数 u,u+m,u−m 是同一个逆元类的不同代表。
我们考虑的模幂运算以整数 a 为底、非负整数 e 为指数,且 m≥2。指数为零的约定是 a0=1,在这个代数计算中底为零时也如此。负指数需要逆元,不在此输入规格之内。输入长度指编码后的整数的二进制位数,并在需要时计入固定的分隔符与符号。
定理/命题
定理 5.1.1
(欧几里得算法计算最大公约数与 Bézout 证书)
对于不全为零的非负整数 a,b,欧几里得算法会终止并返回 d=gcd(a,b)。存在整数 s,t 使得 sa+tb=d。这样的系数可以通过记录并代入各步除法来计算,也可以在更新各个余数的同时更新相应的系数对来计算。
整数 a 在模 m≥2 下有逆元,当且仅当 gcd(a,m)=1。更一般地,同余方程 ax≡c(modm) 有解,当且仅当 d=gcd(a,m) 整除 c。在有解的情形下,它在模 m 意义下恰有 d 个互不相同的解类。
初始化 r=1,b=amodm,q=e。当 q>0 时,若 q 为奇数,则把 r 模 m 乘以 b;把 b 替换为 b2modm;并把 q 替换为 ⌊q/2⌋。终止时,r 是 ae(modm) 的规范代表。当 e 有 k 个二进制位时,该过程使用 O(k) 次模乘法;指数为零时不需要任何乘法。
最后一个定理中各条指令的顺序至关重要。奇数情形的更新使用的是旧的 b,即在对它平方之前。也可以作为优化而省去最后一次不被使用的平方,但下面的证明针对的是所陈述的过程。依据一个确切的赋值序列来书写不变量,可以避免含糊的算法获得一个看似严谨的证明。
证明思路或证明
证明
(欧几里得算法:不变量、终止与 Bézout 证书)
若 a=qb+r,则一个整数整除 a,b 两者,当且仅当它整除 b,r 两者。一个方向用到 r=a−qb,另一个方向用到 a=qb+r。因此,欧几里得的每一步更新都保持全部公约数构成的集合不变,从而也保持其中最大的正元素不变。当第二个坐标为正时,它严格递减,所以由良序原理可知算法终止。在最终数对 (d,0) 处,最大公约数是 d,这就证明了正确性。
每个初始坐标都是原始输入的整数组合:a=1a+0b 且 b=0a+1b。每当两个余数是这样的组合时,把其中一个乘以商后再相减,所得的差也是这样的组合。因此最后一个非零余数具有 sa+tb 的形式。这是证书的一个构造性证明,而不是断言适当的系数“总会存在”。要实现它,为当前的两个坐标各存储一个系数对,并对这些系数对施行同样的减法。
概念视角结构
最大公约数是所有整数组合的生成元
设 a,b 不全为零,则集合 {sa+tb:s,t∈Z} 对加法和取负都封闭,所以它恰由其最小正元素的全部倍数组成。这个元素同时整除 a 和 b,又是它们的组合,因此每个公因数都整除它:它就是 gcd(a,b)。用这个描述来看,a 在模 m 下可逆,当且仅当 1 是 a 与 m 的组合。
若 au+mv=1,则模 m 约化得 au≡1。当最大公约数为一时,Bézout 恒等式提供了这样的 u,v。反之,若有逆元,则存在整数 v 使得 au−1=mv,所以 a,m 的每个公约数都整除一。这就在两个方向上证明了逆元存在的判别准则。
对于一般的同余方程,任何解都给出 ax−c=mv,所以 d 必须整除 c。当它整除时,把整数等式除以 d,得到
(a/d)x≡c/d(modm/d).两个新的系数 a/d 与 m/d 互素,所以在模 m/d 下恰有一个解类。若 m/d=1,这只是说每个整数都满足约化后的同余式;此时不需要模数为一的逆元定理。无论哪种情形,代表该类的整数在模 m 下恰好分裂为 d 个类,可用 x0+j(m/d)(0≤j<d)作代表。所列出的互异代表之差小于一个完整的模数,因而不可能同余。每个解都与其中之一同余。
对于重复平方法,维持
rbq≡ae(modm).它在初始时成立。把旧指数写成 q=2h+ε,其中 ε 为零或一。更新后的状态为 r′=rbεmodm,b′=b2modm,q′=h,所以 r′(b′)q′≡rb2h+ε=rbq。因此不变量得以保持。非负的指数不断减小直至为零。此时它的幂贡献为一,留下 r≡ae;每次乘法之后做约化,使 r 保持规范形式。
证明透视
保留信息,缩减参数
欧几里得算法在使余数减小的同时保持公约数集合不变。重复平方法在缩短指数的同时保持乘积不变。在每个证明中,信息的保持确立部分正确性,而递减的参数确立终止性。仅有递减的参数只能说明程序会终止;一个很快返回错误答案的程序同样可能具有递减参数。
例题详解
例题 5.1.4
(一次最大公约数计算同时回答了一个不可能性问题)
计算 252=1⋅198+54,198=3⋅54+36,以及 54=1⋅36+18,随后是 36=2⋅18。最大公约数为十八。反向代入得 18=54−36=4⋅54−198=4⋅252−5⋅198。这个恒等式无需重复搜索便可检验结果。它还证明了 252x≡1(mod198) 不可能成立:十八整除左边的每个值以及模数,却不能整除一。
对于 17 与 43,除法为 43=2⋅17+9,17=9+8,9=8+1。因此 1=9−8=2⋅9−17=2⋅43−5⋅17。系数负五给出模 43 的逆元类 38,并且 17⋅38=646=15⋅43+1。对于另一个同余方程,6x≡8(mod14) 除以最大公约数二后化为 3x≡4(mod7)。由于三在模七下的逆元是五,故 x≡20≡6(mod7)。模十四的两个解是六和十三。检验可知,36 与 78 的余数都是八。
要计算 713mod23,使用 13=8+4+1。逐次平方得到的剩余是 7、3、9 和 12,分别对应一次、二次、四次和八次幂。把所选的剩余相乘,得 7⋅9⋅12=756≡20(mod23)。按所陈述的循环,状态 (r,b,q) 初始为 (1,7,13),接着依次是 (7,3,6)、(7,9,3)、(17,12,1) 和 (20,6,0)。不变量解释了为什么跳过偶数指数时的乘法不会损失任何信息。b 的最终值六并未被使用,所以实现中可以省略最后一次平方。
要分析欧几里得算法,首先安排 a≥b>0,并设两个输入至多有 L 位。每两个余数步骤,正的余数至少缩减为原来的一半。事实上,对于连续的正余数 u>v>r,若 v≤u/2,则缩减已经发生;否则商为一,于是 r=u−v<u/2。因此共有 O(L) 次除法。若采用普通长除法,每次为 O(L2) 次位运算,则保守的上界为 O(L3)。这是一个有效的多项式上界,并不声称是实现所能达到的最优界。
对于模幂,设底数已经按一个 L 位的模数约化。剩余至多有 L 位,乘积至多有 2L 位。竖式乘法再加长除法,每次模乘法的代价为 O(L2) 次位运算。因此 k 位的指数使主循环需要 O(kL2) 次位运算,前提是通过移动索引逐位读取指数,而不是反复复制整个剩余商。读入并首次约化一个长得多的底数,还需要取决于该底数长度的额外代价。存储常数个剩余所需的空间为 O(L) 位;若显式保留指数,则另需 O(k) 位。
常见错误
反例模式
消去不可逆的因子
一条诱人的规则说:由 cx≡cy(modm) 可推出 x≡y(modm)。取 c=2,m=6,x=1,y=4:cx=2,cy=8≡2(mod6),所以假设成立,但 x−y=−3 不能被六整除。当 gcd(c,m)=1 时规则成立,因为乘以 c 的逆元保持等价性。一般地,设 d=gcd(c,m),写 c(x−y)=mk 并除以 d:互素的 c/d 与 m/d 迫使 m/d∣x−y,所以消去只能给出 x≡y(modm/d)。此例中 1≡4(mod3)。
扩展欧几里得算法给出的逆元系数可能为负;在 17 与 43 的例子中它是 −5。把它约化到 0,…,m−1(此处为 38)改变的是其代表,而不是其剩余类。各种编程语言对带符号余数的约定不同,所以当输入可能为负时,应当显式地实现数学上的规范余数。
一个循环迭代 e 次,并不会仅仅因为循环变量被称为指数就成为关于 log2e 的多项式。反过来,统计出 O(loge) 次乘法,也不能说明计算完整的整数 ae 只需关于输入长度的多项式空间:该完整输出可能有指数多位数字。在这里,是模约化使中间值保持有界。
总结
余数保留公约数并使欧几里得算法终止;追踪它们的线性组合则产生可检验的 Bézout 恒等式。该恒等式刻画了模逆元,并解决所有线性同余方程。重复平方法在消耗指数位的同时保持一个乘积不变量。一旦明确陈述所保留的信息、输入编码与算术模型,正确性与效率都会变得更加清晰。
练习
练习 5.1.7
(计算 gcd(99,78),并求整数 s,t 满足 99s+78t=gcd(99,78)。)
核心
解答(3)
1逐步做除法
99=78+21,78=3⋅21+15,21=15+6,15=2⋅6+3,6=2⋅3。最后一个非零余数是 3。
2反向代入
3=15−2⋅6=3⋅15−2⋅21=3⋅78−11⋅21=14⋅78−11⋅99。
3写出证书
最大公约数为三,一组系数为 (s,t)=(−11,14);确实 −1089+1092=3。
快速检查
(求解 9x≡6(mod15),列出模十五的每一个解类。解释为什么 9x≡4(mod15) 无解。)
解答 · 答案
最大公约数为三,故除以它得 3x≡2(mod5)。三的逆元是二,因此 x≡4(mod5)。它在模十五下的三个类是四、九和十四。第二个同余式不可能成立,因为三不整除四。
快速检查
(通过逐次平方的剩余计算 311mod17,并陈述指数为零时的不变量。)
解答 · 答案
一次、二次、四次和八次幂对应的剩余是 3,9,13,16。由于 11=8+2+1,答案为 16⋅9⋅3≡7(mod17)。当 q=0 时,不变量写作 r≡311(mod17),所以返回的规范剩余是七。
快速检查
(某个拟议的实现在应用奇数情形的乘法之前先对 b 平方。证明它在指数为一时失败,并说明如何修复。)
解答 · 答案
从 (1,amodm,1) 出发,先平方会使奇数情形的更新使用 a2 而不是 a。取 a=2,m=5,错误的答案是四而不是二。应当在奇数更新中使用旧的底数,或者为一个刻意不同的算法另行推导不同的不变量。
快速检查
(当指数为 2k 时,比较重复乘法与重复平方法。区分指数的数值与其二进制编码长度。)
解答 · 答案
重复乘法使用约 2k 次乘法。重复平方法使用约 k 次;2k 的编码有 k+1 位。在做模约化的情况下,每次乘法的代价也是关于模数长度的多项式。若不做约化,则必须另行计入不断增长的输出规模。