清华大学：《算法分析与设计》课程讲义_第10讲 Number theoretic Algorithm

From useless to useful Lecture 10 Number Number theory is regarded as a beautiful but largely useless in the past theoretic Algorithn a Today number-theoretic algorithms are used videly 清华大学 Contents Basic Concepts ers整数 a Divisibility and divisor n Prime and composite numbers mN={0,123.} Natural numbers自然数 rd|a( d divides a)d整除a,存在整数k使得 a Greatest common divisors a=kd a Relative prime integers Divisor:约数 n Euclid algorithm and its complexity analysis a Trivia| divisor:平凡约数【举例】 n Modular arithmetic a Solving modular linear equation m素数【1,2,3,4那个是素数】 ■孙子定理【中国剩余数定理】 m合数【1,2,3,4那个是合数】 手大学想 与算法复杂度相关的概念 除法定理 ■整数的表示: 对任意整数a和正整数n,存在唯一整数q和r使 一进制 得0≤rcn,a=qn+r 二进制【十进制等】的长度作为一个整数的复 Quotient:【q】 杂度度量 a Remainder(residue【r】) s The function of Log*of n a fo(n)=n if i==0 zn={al:0≤a≤n1} fo(n)=f(fo(n) if i>0 [aln=a+kn: k in Z Ig n= mini=0: Ig(n)<=11 【[aJn的代表?】 大学证制

1 清华大学 宋斌恒 1 Lecture 10. Number theoretic Algorithm 清华大学 宋斌恒 清华大学 宋斌恒 2 From useless to useful „ Number theory is regarded as a beautiful but largely useless in the past „ Today number-theoretic algorithms are used widely 清华大学 宋斌恒 3 Contents „ Basic concepts „ Divisibility and divisor „ Prime and composite numbers „ Division theorem „ Greatest common divisors „ Relative prime integers „ Unique factorization „ Euclid algorithm and its complexity analysis „ Modular arithmetic „ Solving modular linear equation „ 孙子定理【中国剩余数定理】 „ RSA 清华大学 宋斌恒 4 Basic Concepts „ Z={…,-2,-1,0,1,2,…} Integers 整数 „ N={0,1,2,3…} Natural numbers 自然数 „ d|a (d divides a) d整除a， 存在整数k使得 a=kd „ Divisor: 约数 „ Trivial divisor：平凡约数【举例】 „ 素数【1，2，3，4那个是素数】 „ 合数【1，2，3，4那个是合数】 清华大学 宋斌恒 5 与算法复杂度相关的概念 „ 整数的表示： „ 一进制 „ 二进制【十进制等】的长度作为一个整数的复 杂度度量。 „ The function of “Log * of n” „ f (i)(n)=n if i==0 „ f (i)(n)=f(f(i)(n)) if i>0 „ lg* n = min{i>=0: lg(i)(n)<=1} 清华大学 宋斌恒 6 除法定理 „ 对任意整数a和正整数n，存在唯一整数q和r使 得 0≤r<n, a=qn+r „ Quotient:【q】 „ Remainder (residue 【r】) „ Zn ={[a]n: 0≤a≤n-1} „ [a]n ={a+kn: k in Z} „ 【 [a]n的代表？】

最大公约数 oC Gcd greatest common devisors GCD递推定理:gcd(ab)=gcd(b, a mod b) ■定理:如果a和b是任意不等于0的整数,则 ■辗转相除法【如何说明其正确性?】 gcd(ab)=集合ax+byx,yin2}的最小整数 【证明!】 存在x和y使得 gcd(a, b)=xa+yb 互素: Relative prime integers ■西方人叫 Euclid算法 如果gcd(a,b)=1称a和b互素 ■唯一分解定理 法i e,p是素数单调升【是否可以通过 ■?如何证明有无穷多素数??【课堂提问】 清手大学城想 Euclid算法 扩展欧几里德算法 Euclid(a, b) Extended-Euclid(a, b) a If b=0 then return(a, 1, 0) Retum Euclid(b, a mod b) a(d, x, y)Extended-Euclid(b, a mod b) Steps of division: o(Ig a)=o(n) n is the bit length of Lame' s theorem:欧几里德算法迭代步数小于k,其 中F是第k个 Fibonaco数 证明提示:数学归纳法证明:如果a>b>=1而且上述 Euclid算法进行了k步递归,则a>=Fk*2andb>=F*t 手大学想 计算最大公约数及其线性组合表示 群的概念 b [a/b d x y 群(S,⊕) 91491 7 -1 2 X-a/bly 元 49421 -1 x-a/bly' 3.结合率 4276 701×-{a/b] 逆元 交换率:交换群= Abelian群 大学证制

2 清华大学 宋斌恒 7 最大公约数 „ Gcd: greatest common devisors „ 定理：如果a和b是任意不等于0的整数，则 gcd(a,b)=集合{ax+by:x,y in Z}的最小整数。 【证明！】 „ 互素：Relative prime integers „ 如果gcd(a, b)=1称a和b互素 „ 唯一分解定理 „ a=Πi=1,…n (pi ei), pi 是素数单调升【是否可以通过 此方法计算gcd? 复杂度？】 „ ？如何证明有无穷多素数？？【课堂提问】 清华大学 宋斌恒 8 gcd „ GCD递推定理：gcd(a,b)=gcd(b,a mod b) „ 辗转相除法【如何说明其正确性？】 „ 存在x和y使得 gcd(a,b)=xa+yb。 „ 西方人叫Euclid算法 清华大学 宋斌恒 9 Euclid算法 1. Euclid(a,b) 1. If b==0 return a 2. Return Euclid(b,a mod b) „ Running time: „ Steps of division: O(lg a) = O(n) n is the bit length of a. „ Lame’s theorem: 欧几里德算法迭代步数小于k，其 中Fk是第k个Fibonacci数。 „ 证明提示：数学归纳法证明：如果a>b>=1而且上述 Euclid算法进行了k步递归，则a>= Fk+2 and b>= Fk+1 清华大学 宋斌恒 10 扩展欧几里德算法 „ Extended-Euclid(a,b) „ If b=0 then return (a,1,0) „ (d’,x’,y’)ÅExtended-Euclid(b,a mod b) „ Return (d’,y’,x’-[a/b]y’); 清华大学 宋斌恒 11 计算最大公约数及其线性组合表示 a b [a/b] d x y 140 91 1 7 2 -3 91 49 1 7 -1 2 x’-[a/b]y’ 49 42 1 7 1 -1 x’-[a/b]y’ 42 7 6 7 0 1 x’-[a/b]y’ 70- 710 清华大学 宋斌恒 12 群的概念？ „ 群(S，⊕ ) 1. 封闭性 2. 么元 3. 结合率 4. 逆元 交换率：交换群＝ Abelian群

Modular arithmetic 5群 +n群 n群 (2n+)是有限Abe群 m其中Zn={aln:gcd(an)=1} 12478134 清手大学城想 Euler's phi function 由一个元素生成[张成]的子群 d(n)=nILp(1-1/p) is the size of z欧拉ψ函数 Lagranges theorem:有限群的子群的元素个 Order of a:使a=e的最小k 数是原群元素个数的约数 手大学想 Solving modular linear equation 孙子点兵【中国余数定理】 ax≡b(modm 表示由a生成的Zn的子群 ma→(a1,a2……a), →=cd>inzn sa>l=n/d n=n1n2…nk所有n两两互素 利用扩充欧拉算法求解上述问题,可以得到有无解,有解 Zn与Zn1×Zn2×…×Zmk等价 时给出所有解 m求逆与系数。 如果d则有b个解,x=x(b/d)modn,x是扩展欧几理 a=e am(m-l mod n) 德算法的系数 x+nd)modn;i=0,d-1通解 -ny 其中m( m:-1 mod n)是基本解

3 清华大学 宋斌恒 13 Modular arithmetic „ ＋n群， „ ×n群 „ (Zn,+n)是有限Abel群 „ (Z* n,×n)是有限Abel群 „ 其中Z* n ＝{[a]n : gcd(a,n)=1} 清华大学 宋斌恒 14 . 15群 14 13 11 8 7 4 4 1 2 4 1 .15 1 2 4 7 8 11 13 14 清华大学 宋斌恒 15 Euler’s phi function φ(n)=nΠp|n(1-1/p) is the size of Z* n. 欧拉φ函数 „ 子群，真子群， „ Lagrange’s theorem: 有限群的子群的元素个 数是原群元素个数的约数。 清华大学 宋斌恒 16 由一个元素生成[张成]的子群 „ 幂： „ a(k)= a ⊕ a ⊕ a ⊕ a ⊕ …⊕ a „ ={a(k), k>=1} „ Order of a: 使a(k)＝e的最小k 清华大学 宋斌恒 17 Solving modular linear equation „ ax ≡ b (mod n) „ 表示 由 a 生成的Zn的子群 „ d=gcd(a,n) „ Î= in Zn. „ ||=n/d „ 利用扩充欧拉算法求解上述问题，可以得到有无解，有解 时给出所有解。 „ 如果d|b则有b/d个解，x0=x’(b/d) mod n, x’是扩展欧几理 德算法的系数 „ x0+i(n/d) mod n; i=0,…,d-1通解 清华大学 宋斌恒 18 孙子点兵【中国余数定理】 „ a ÅÆ(a1,a2,…,ak)， „ a in Zn, „ ai in Zni , „ n= n1n2…nk 所有ni 两两互素 „ Zn 与Zn1× Zn2×… × Znk.等价 „ 求逆与系数。 „ a=Σ ai mi (mi -1 mod ni ), „ mi =n1n2…ni-1ni+1…nk „ 其中mi (mi -1 mod ni )是基本解

鬼谷算题 解答 ■在鬼谷算题中有这样一个著名的题目:“今有物 m3个一排余2 不知其数,三三数之剩二,五五数之剩三,七 m5个一排余3 七数之剩二,问物几何?” m7个一排余2 ■我国宋代学者对这类题目钻研己颇为精深,总 结出了“三人同行七十稀,五树梅花廿一枝,七 ■【2】×70+【3】×21+【2】×15-105= 子团圆正半月,去百零五便得知。”这样的口 诀,意思是说“以三三数之,余数乘以七十:五 三人同行70稀,五树梅花廿一支,七子团圆正半 五数之,余数乘以二十一:七七数之,余数乘 月,抛五去百便得知 十五。三者相加,如不大于一百零五,即为答 数:否则须减去一百零五或其倍数。 清手大学城想 利用公式求基本解 元素的幂 35×(35-1mod3)=70 a 3 mod 7 21×(21-1mod5)=21 a Eulers theorem 15×(15-1mod7)=15 For any integer n >1 m更多内容参见论文《中国剩余定理》 a≡1(modn) for all a in Z 数学研究所李文林袁向东 a Fermat's theorem .a-1=1(mod p)for all a in zp 如何计算a(modn)?见下页 手大学想 MODULAR EXPONENTIATION(a, b, n) 密码学 c←0 明文m be the binary rep. of b for i+k downto 0 tc←2c 解密函数D ae=Em),要求 d-(d·a)modn a m=Dk(e) return d 【复杂度?】 大学证制

4 清华大学 宋斌恒 19 鬼谷算题 „ 在鬼谷算题中有这样一个著名的题目：“今有物 不知其数，三三数之剩二，五五数之剩三，七 七数之剩二，问物几何?” „ 我国宋代学者对这类题目钻研已颇为精深，总 结出了“三人同行七十稀，五树梅花廿一枝，七 子团圆正半月，去百零五便得知。”这样的口 诀，意思是说“以三三数之，余数乘以七十；五 五数之，余数乘以二十一；七七数之，余数乘 十五。三者相加，如不大于一百零五，即为答 数；否则须减去一百零五或其倍数。 清华大学 宋斌恒 20 解答 „ 3个一排余2、 „ 5个一排余3、 „ 7个一排余2、 „ 【2】×70＋【3】×21＋【2】×15－105＝ 128 „ 三人同行70稀, 五树梅花廿一支, 七子团圆正半 月, 抛五去百便得知 。 清华大学 宋斌恒 21 利用公式求基本解 „ 35×（35－1 mod 3）＝70 „ 21×（21－1 mod 5）＝21 „ 15×（15－1 mod 7）＝15 „ 更多内容参见 论文《中国剩余定理》 „ 数学研究所 李文林 袁向东 清华大学 宋斌恒 22 元素的幂 „ 3i mod 7 „ Euler’s theorem: „ For any integer n >1. „ aφ(n) ≡ 1 (mod n) for all a in Z* n . „ Fermat’s theorem: „ ap-1 ≡ 1 (mod p ) for all a in Z* p. „ 如何计算 ab (mod n)？见下页 清华大学 宋斌恒 23 MODULAR￾EXPONENTIATION(a,b,n) 1 c←0 2 d ←1 3 let be the binary rep. of b 4 for i ← k downto 0 1 c ← 2c 2 d ← (d • d) mod n 3 if bi = 1 then 1 c ← c + 1 2 d ← (d • a) mod n 5 return d 【复杂度？】 清华大学 宋斌恒 24 密码学 „ 对称加密： „ 明文 m „ 密文 e „ 密钥 k „ 加密函数 Ek： „ 解密函数 Dk： „ e=Ek(m), 要求 „ m=Dk(e) „ Dk Ek=I

经典与现代对称加密算法 非对称加密算法 字符移位 ■解决对称加密算法在分布系统中的密钥 ■字符置换 人通讯,需要每个人记载n个密码,秘码 每个人有一个(公钥,私钥)对,其中公 布到任何地方。每个人只需要保存自己的私 利用公钥加密可以用私钥解密,反之亦然 a可以验证信息的发送人 保证只有信息的接收人才能得到消息 清手大学城想 公钥理论 RSA算法 ■理论上要达到以上要求,公钥和私钥是可以互 m取2个不等的大素数pq,如其长度为512【或更 相确定的,即给定公钥可以求出私钥,反 长】位 然,如果给定公钥能求出私钥,那公钥体系岂 计算n=pq 不没有任何意义! 选择较小的奇数e,它和◆n)=(p-1)(q-1)互素 ■问题是:理论上要存在,而实际上不可算,就 计算e在模◆n)下的逆d 能达到目标。 发布(e,n)作为公钥 保存(dn)作为私钥 手大学想 RSA加密算法 RSA被攻击的可能性 n A message m is a number in zn 由于(en)公开,从(e,n)计算dn) m用公钥转换:P(M)=Me(modn) 目前没有发现比分解n=pq更为容易的算法,而 用私钥转换:S(M=M(modn) 因式分解是NPC问题,故目前攻击困难 ■定理:PS(M=SP(M)=M m两次转换的复杂性:如果n的长度是k,则需要lge+lgd 的长度是k的数的乘法,若乘法复杂度为长度的平 方,则整个复杂度为K3。如果k=1024则需要1gga的 运算量。 大学证制

5 清华大学 宋斌恒 25 经典与现代对称加密算法 „ 字符移位 „ 字符置换 „ DES „ 双重DES 清华大学 宋斌恒 26 非对称加密算法 „ 解决对称加密算法在分布系统中的密钥管理缺陷：n个 人通讯，需要每个人记载n个密码，秘码存储量总数为 n2。 „ 工作原理：每个人有一个（公钥，私钥）对，其中公 钥可以发布到任何地方。每个人只需要保存自己的私 钥即可，其中要求： „ 利用公钥加密可以用私钥解密，反之亦然， „ 可以验证信息的发送人 „ 保证只有信息的接收人才能得到消息等 清华大学 宋斌恒 27 公钥理论 „ 理论上要达到以上要求，公钥和私钥是可以互 相确定的，即给定公钥可以求出私钥，反之亦 然，如果给定公钥能求出私钥，那公钥体系岂 不没有任何意义！ „ 问题是：理论上要存在，而实际上不可算，就 能达到目标。 清华大学 宋斌恒 28 RSA算法 „ 取2个不等的大素数p,q, 如其长度为512【或更 长】位 „ 计算n=pq „ 选择较小的奇数e，它和φ(n)＝(p-1)(q-1)互素 „ 计算e在模φ(n)下的逆d „ 发布(e,n)作为公钥 „ 保存(d,n)作为私钥 清华大学 宋斌恒 29 RSA加密算法 „ A message m is a number in Zn, „ 用公钥转换：P(M)=Me (mod n) „ 用私钥转换：S (M)=Md (mod n) „ 定理：PS(M)=SP(M)=M „ 两次转换的复杂性：如果n的长度是k，则需要lge＋lgd 次的长度是k的数的乘法，若乘法复杂度为长度的平 方，则整个复杂度为k3。如果k=1024,则需要1 giga的 运算量。 清华大学 宋斌恒 30 RSA被攻击的可能性 „ 由于(e,n) 公开，从(e,n)计算(d,n) „ 目前没有发现比分解n＝pq更为容易的算法，而 因式分解是NPC问题，故目前攻击困难

RSA算法的应用 实现RSA算法体系要做的工作 ■不可抵赖性:Aice发信给Bob,如何保证 m大整数的表示 Bob有充分的理由证明此信是Ace发出而不是 m如何任意选取两个大素数(512、1024甚至2048位的 他人?任何人包括Aice不能否认这是Ace发出 素数)? 的信息 蓬定要是·一数试覓以舒证以足够大的概 ■大整数的加法运算和模加运算 ■大整数的乘法运算和模乘运算 Divide and Conquer可以得到on3)复杂度的乘法 ■幂乘算法的实现 清手大学城想 RSA及其它加密算法的克星 密码系统需要防范的攻击 ■干草堆里找针(大海捞针) Find a needle in a stack of hay,量子计算机可以在sqrt(n)的时间 1.监听与分析 2伪造其中一方(服务器或客户端) 内找到n个散乱数字中的某一个 3.代理(在线路中伪造双方) ■大海捞针:大海里有一根针,需要判断它存在 的位置,如果你有一个具有魔法的吸铁石,可 窜改 以在一秒内判断任何区域内有没有针,则你可 5.重放 以在非常短的时间内把针找到! 综合 ■非确定图灵机可以做到这一点 手大学想 密码系统要考虑的问题 安全协议介绍 ■随机数 ■如何利用对称加密系统实现安全通话: ■哈希函数 设k是双方共享的秘密,可以利用此实现抗击前 ■对称加密算法 面提到的各种攻击 ■非对称加密算法 Alice:生成随机数r1,「2,发送 ■密码协议 (r1,des(k,n2))给Bob Bob:生成随机数r3,r4,发送 (r3,des(k,r4))给Aice 大学证制

6 清华大学 宋斌恒 31 RSA算法的应用 „ 不可抵赖性：Alice 发信给 Bob，如何保证 Bob有充分的理由证明此信是Alice发出而不是 他人？任何人包括Alice不能否认这是Alice发出 的信息。 清华大学 宋斌恒 32 实现RSA算法体系要做的工作 „ 大整数的表示 „ 如何任意选取两个大素数（512、1024甚至2048位的 素数）？ „ 没有直接方法可用，利用测试法可以保证以足够大的概 率保证选定的数是一个素数，参见p887.- „ 大整数的加法运算和模加运算 „ 大整数的乘法运算和模乘运算 „ Divide and Conquer 可以得到O(nlg 3 )复杂度的乘法 „ 幂乘算法的实现。 清华大学 宋斌恒 33 RSA及其它加密算法的克星 „ 干草堆里找针（大海捞针）Find a needle in a stack of hay, 量子计算机可以在sqrt(n)的时间 内找到n个散乱数字中的某一个。 „ 大海捞针：大海里有一根针，需要判断它存在 的位置，如果你有一个具有魔法的吸铁石，可 以在一秒内判断任何区域内有没有针，则你可 以在非常短的时间内把针找到！ „ 非确定图灵机可以做到这一点 清华大学 宋斌恒 34 密码系统需要防范的攻击 1. 监听与分析 2. 伪造其中一方（服务器或客户端） 3. 代理（在线路中伪造双方） 4. 窜改 5. 重放 6. 综合 清华大学 宋斌恒 35 密码系统要考虑的问题 „ 随机数 „ 哈希函数 „ 对称加密算法 „ 非对称加密算法 „ 密码协议 清华大学 宋斌恒 36 安全协议介绍 „ 如何利用对称加密系统实现安全通话： „ 设k是双方共享的秘密，可以利用此实现抗击前 面提到的各种攻击： „ Alice：生成随机数r1，r2，发送 (r1，des（k，r2））给Bob „ Bob：生成随机数r3，r4，发送 (r3，des（k，r4））给Alice

续 分布授权、验证 Aice:发送h(r3k)给Bob a Alice授权给Bob,Bob以Aice的授权身份给 Bob:发送h(1k)给Ace Car发送消息,Car从 Alice处得到验证 mAce:验证收到的值是否与h(r1,k)相等 ■公钥实现:要求授权只能由Bob使用。 mBob:验证收到的值是否与h(r3,k)相等 ■如果相等则双方互相验明共享秘密,然后利用其秘密k aAce发送用自己私钥和Bob公钥加密的授权书 解密互相发送过来的随机数r2和4作为大家会话密钥 给Bob,Bob解密可以得到授权书 分析! Bob用自己私钥和ca公钥发送授权书到car car发送授权书到Aice即可验证 清手大学城想

7 清华大学 宋斌恒 37 续 „ Alice：发送h(r3,k)给Bob „ Bob：发送h(r1,k)给Alice „ Alice：验证收到的值是否与h（r1，k）相等 „ Bob：验证收到的值是否与h（r3，k）相等 „ 如果相等则双方互相验明共享秘密，然后利用其秘密k 解密互相发送过来的随机数r2和r4作为大家会话密钥 „ 分析！ 清华大学 宋斌恒 38 分布授权、验证 „ Alice授权给Bob，Bob以Alice的授权身份给 Carl发送消息，Carl从Alice处得到验证。 „ 公钥实现：要求授权只能由Bob使用。 „ Alice发送用自己私钥和Bob公钥加密的授权书 给Bob，Bob解密可以得到授权书 „ Bob用自己私钥和Carl公钥发送授权书到Carl， Carl发送授权书到Alice即可验证