计算机问题求解 – 论题4-2 - 数论算法 2017年3月27日

问题1: 讨论数论算法的复杂性有 什么特殊之处?为什么? 想想两个“很大很大”的整数相乘。 对n的理解，对开销衡量的基本操作 基本的算术操作不能再被看做一个计算耗时，用二进制编码后的位计算作为基本单元更为合理 想想两个“很大很大”的整数相乘。

“长乘” 问题2： 你能解释以下 下面的论断吗？

可能是世界上最古老的算法 证明两个数可以互相整除即可 d是a的因子，也是b的因子，也就是a-qb的因子，是a mod b的因子，因此是gcd(b,a mod b)的因子 证明的关键：a mod b 可以表示为a和b的线性组合：a-qb；所以gcd(a,b)可以整除(a mod b), 所以可以整除gcd(b, a mod b)；类似地可以证明后者也可以整除前者，两者均为正，所以相等。

问题4：如何观察这个算法的复杂度？ 4.1：Euclid算法的复杂度如何评估？ 4.2：它与Fibonaci序列有巧合吗？这种 巧合是偶然还是必然？ 4.1：看a和b的大小，而不是输入数据的数量大小；统计递归调用的次数和a,b大小的关系

这个定理的直观含义是什么？ 小数字越大，算法的递归调用次数越多。

定理的证明

定理11可以由引理10直接得到。Why？ 定理31.11是引理31.10的逆否命题的量化结论 引理的直观解释： 递归调用次数越多，小数字越大。

How to understand the following sentences? Best possible: Euclid(a,b)中，小数字小于Fk+1时，递归次数一定小于k次。会不会总是小于k-1呢？有一个特例说明：不会总是小于K-1： Euclid(Fk+1,Fk): 小数字小于Fk+1,但不小于Fk，它恰好递归调用了K-1次。达到了上界。 但是对于任意的小数字b，真正的界还可以紧致：O(lgb),当然，还可以紧致（练习）

问题5： “扩充”的Euclid算法，扩充了什么？怎么实现 的？这个扩充的结果用处是什么？ 将a，b的线性组合的系数也输出了。两个算法的复杂性是一致的，目的是为后期的模运算服务 一定要用递归的思维方式去理解这个扩充的原理： d=d’; d=ax+by; d’=bx’+(a mod b)y’=bx’+(a-b[a/b])y’=ay’+b(x’-[a/b]y’) 因此可以取：x=y’和y=x’-[a/b]y’ 线性组合的系数可以用于在剩余乘群中元素的逆元素的计算：ax=b(mod(n)): x

Extented-Euclid(a,n)的返回值中的第二个元素x 模n乘法群（n剩余乘群）： 问题6：任给元素a，其逆元素是什么？ ax+ny=1(因为a和n互质). ax=1(mod n). X是a的逆的候选。X是不是属于Zn呢？ X是否和n互质呢？看x和n能否组成结果为1的线性组合。如果能，说明x和n的最大公约数为1，互质。 Extented-Euclid(a,n)的返回值中的第二个元素x （1，x，y）

如果p是素数，Zp *有多少个元素？任取Zp中某个元素a，我们有什么结论？ 为什么我们用这个符号？ 费马定理，欧拉定理 如果p是素数，Zp *有多少个元素？任取Zp中某个元素a，我们有什么结论？

欧拉与费马 顺便问一句: (x)和(x)有什么不同? Pi函数是小于等于x的素数个数 Fi函数是n剩余乘群中元素个数，所有和n互质的元素个数（含1） 对于两个不同素数p， q ，它们的乘积n = p * q 满足φ(n) = (p -1) * (q -1)   Zn = {1, 2, 3,  ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q}   φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1) ＝φ(p) * φ(q) 

线性模方程的解 4x=1 mod 11 8x=7 mod 12 81x=11 mod 213 模运算有强烈的循环特性 有解 无解：8和12的最大公因子为4,7不是4的倍数 无解：81和213的GCD是3,11不是3的倍数； 看不出，但算得出：算12…和84726534…的GCD，看847205136是否是GCD的倍数。 如果a和n互质，一定有解，解唯一：a和n的最小线性组合ax’+ny中的x’乘以b 如果a和n不互质，有GCD d=ax’+ny，如果b是d的倍数，有解，解是：x’（b/d） 122348567x=847205136 mod 8472653495

我们如何入手解决这个问题？ 解方程总可以看成寻找某个特定的元素，加以运算满足方程 这个方程会在哪个群中加以思考？ 总归可以在群概念下思考 Zn还是Zn*? 剩余乘群，对群中元素要求太高（要求a和n互素），会导致很多方程无法讨论。

问题6： 从Z6中取什么样的元素a，可以满足 a恰好就是Z6? 如果选择的a不能生成Zn，那么a有 什么特征？ 观察GCD（a，n） 互素元素 A和n不互素，有GCD>1; 模运算具有极强的对称性，可以用群来刻画其数学性质。 模运算总是会归结到一个有限集合上去讨论，因此我们主要在有限群中讨论 有限群的非空封闭子集必定构成子群。 在Zn剩余加群中，除了单位元，如果a|n，ax=n(ax之间是四则运算中的乘法)，ax=n=0(mod n), x就是<a>子群的阶。如果a和n互质，只有an（此处的an是普通乘法）才能模n为0，an=0(mod n)，a的阶必定是n。 在Zn剩余乘群中，1是单位元。除了1外， 子群的元素个数，也就是a的阶，必定是n的因子！ 如何推广到一般的Zn? 观察GCD（a，n）

直观解释： 在Zn中，任取a，可以构造<a>; 如果a,n互质，<a>=Zn 如果gcd(a,n)=d不为1，构造<d>, <a>=<d>, 而且子群的元素个数为n/d

问题7： 前面的两个问题与方程 axb mod n是否有解以及 解是否唯一有什么关系？

直观解释： 在Zn群中构造a的生成子群，b必须在这个子群中 进而：b应该是gcd(a,n)的倍数！

这两个定理给出了找到所有解的方法：特别关注extended-Euclid算法

ax1 mod n有唯一解与Zn*构成群二者之间有什么联系？ 问题8： ax1 mod n有唯一解与Zn*构成群二者之间有什么联系？ Zn*是群，群中所有元素均和n互质，gcd=1.解就是逆 Z*群中元素必有唯一解。

问题9： 平方，再平方。但如果指数不是2 的整次幂怎么办？ 在模算术中如何求乘幂 把指数变成2进制编码，然后反复平方（注意：从高位到低位遍历） a的21次方：20=（10100） 第一位：1 ====》 a 第二位：0 ====》a2 第三位：1 ====》（a2）2a 第四位：0 ====》（（a2）2a）2 第五位：0 ====》（（（a2）2a）2）2 如果求a21，可以连续平方4次，再乘 a 5次。但也可以先平方两次，乘1次a，再平方两次，再乘1次a，当然后者效率高！

循环不变量： 模运算规则： ab mod n = ((a mod n)b) mod n C性质的保持显而易见 D：当遇到0时：新d=老d平方模n=a的c次幂的平方模n=a的2c次幂模n； 当遇到1时：新d=（老d平方乘以a）模n=a的2c加1次幂模n 都是a的新c次幂模n

如何判定一个数是质数 – 素性判定 问题11： 为什么筛法不是个可行的 算法？ 你设想一下判定一个256位的整数是否是质数？

再看费马定理： 所以，当我们测试所有a时：如果有一个a不满足公式31.40，显然n是合数； 当我们没有发现这样的a时，我们能够说n是素数吗？ 基于2的伪素数

比“筛子”好？ to make believe 问题12： 这个算法的原理是什么，这个原 理是否正确？ 费马定理的逆命题，几乎成立！

Bad News and Good News Good news: 根据经验，这个判定方法出错的概念很小！ Fermat’s Little Theorem的逆命题并不成立： Good news: 根据经验，这个判定方法出错的概念很小！ And bad news again: 1,我们不能通过测试其它的a的方式来杜绝错误； 2，我们一般不可能知道结果是错的！

课外作业 TC Ex.31.1-: 12, 13 TC Ex.31.2-: 4, 5, 6, 9 TC Ex.31.3-: 5

Open Topics 用分治法写出n位整数相乘的Θ（nlg3）算法并分析你的结果