《计算复杂性与抽象代数基础》由会员分享，可在线阅读，更多相关《计算复杂性与抽象代数基础（40页珍藏版）》请在金锄头文库上搜索。
1、第六讲 计算复杂性与抽象代数基础上海交通大学计算机系龙宇http:/ 计算复杂性 半群群子群 环整环 Euclid整环 有限域内容问题与算法的复杂性 问题 Q：需要回答的一般性提问Z 该问题的全面描述和有关参量Z 陈述 “解 ”必须满足的性质 问题的实例：将问题的所有参数赋值后所得的特例 问题的规模：或称输入长度，是为解决问题的实例所需输入变量的个数，或者输入二元数据的位数 算法：解决某问题 Q的一系列基本步骤或程序算法复杂性及分类 算法复杂性：执行算法所花费的时间或空间代价：时间复杂度和空间复杂度 时间复杂性：简单的说，是解决问题 Q的任意实例所花费的最大值 算法复杂性 T(n)是 g(n)
2、量级：指存在常数 c和 n1，使得 n n1时，均有 |T(n)| c|g(n)|。记为 T(n)=O(g(n)例： T(n)=kn2+n+1=O(n2)O(n!+n50)=O(n!)O(1)：常数， O(n):线性； O(n2) ：二次； O(cn):指数O(nc):多项式时间； O（ nlog n）：亚指数时间问题的复杂性及分类 问题的复杂性：简单的说，是解决问题的所有算法中复杂度最小值 P问题：问题 Q可以用确定性图灵机在多项式时间内解决 NP问题：问题 Q可以用非确定性图灵机在多项式时间内解决 NPC问题：问题 Q是 NP的，且存在多项式时间内确定性算法能将任意 NP问题规约到该问题
3、P?=NP计算复杂性与密码学的关系 单向函数 (one way function)：Z 是函数 f: AB， f(x)=y Z 由任意 x A求 y容易 （ P）Z 由 “几乎所有 ”y求 x是极为困难的 （ NP） 陷门单向函数Z 由 x计算 f(x)=y很容易 （ P）Z 由 y计算 x很困难 （ NP）Z 当某个陷门 (trapdoor) k给定，由 y, k计算 x容易 （ P） P NP是密码学的必要条件，但不是充分条件一些概念 可忽略的量 (negligible quantity)a function E (n): NR is said to be a negligible qua
4、ntity in n if its reciprocal is a non-polynomially-bounded quantity in n 不可忽略的量 : 1- E (n)半群 半群的定义（ G, ）， G非空Z 封闭性Z 结合律 交换半群 单位元 逆元群的基础知识 群的定义 ：（ G, ）Z 封闭性Z 结合律Z 单位元：唯一性Z 逆元 有限群与无限群 Abelian群（阿贝尔群）：交换群 群同构： f： G G， f(ab)=f(a)f(b)为双射 例子Z 例1 ： (Z/Q/R/C， +) 单位元 /逆元 是无限群， abelian群Z 例2 ： (Q*/R*/C*， ) 单位元
5、/逆元 无限群， abelian群 Z*在下不是群Z 例3 : n个元素的置换组成的集合，置换复合函数 群满足消去定律a,b,c属于群 G，则若 ab=ac,有 b=c子群 定义Z （ G, ）是群Z H是 G的非空子集Z H在 运算下仍是群Z 记做 H G例 : 在 +运算下（ 1） Z Q R C（ 2） 0,偶数 Z 群的任意个子群的，仍然是群（子群） 但子群的一般不是子群 子集生成的子群群 /群元素的阶与循环群 群的阶Z 有限群（ G, ）中，集合元素的个数，记为 |G| 群元素的阶Z a G,|a|为使 ak=e的最小 k,记为 |a|Z ad=e, k|d H G,则一定有 |H|
6、 | |G| (Lagrange定理） 推论 1： a G，则 |a| | |G|, |a|代表 a的阶，也等于 a所生成子群的阶 推论 2； a G, |a|=n, 则 |ak|=n/(n,k) 循环群Z 群（ G, ）， a G, ai=aaa; a0=e； a-n=(a-1)nZ G=(a)=a0,a1,an-1， |G|=|a|Z 分类 无限循环群，阶为无穷大 有限循环群， n阶， |a|=|(a)|=n例 ：（ Z, +）是无限循环群环 定义： （ R， +, ）Z （ R, +）是交换群（封闭、可结合、逆元、交换）Z （ R, ）是半群（封闭、可结合）Z 对 +满足分配律 零元：
7、+的单位元，记为 0，任意 a R,0a=0 单位元：一般指 的单位元 交换环：指对满足交换性 a R, ka=a+a+a (k个 a相 +） a R, ak=a a a (k个 a相）环举例 例1 ：整数、有理数、实数、复数对加法和乘法（数环） 例1 ：实数上 n阶方阵的集合对加法和乘法 例2 ：偶整数集合（正、负、 0）对普通加法和乘法 例3 ：多项式环，设 A为数环多项式集 Ax=a0+a1x+a2x2+anxn+ 定义为 (a0,a1,)+(b0,b1,)=(a0+b0, a1+b1, )定义为 (a0,a1,) (b0,b1,)=(c0, c1,)kijijkcab+=环的零因子与环
8、的特征对于环（ R， +, ） 零因子： a,b R,且 a,b 0, 若 ab=0， a是 R的左零因子， b是 R的右零因子，即是左零因子又是右零因子的元素称为 R的零因子 无零因子：可等价的描述为： a,b R, if ab=0, then a=0 or b=0 特征：对于环（ R， +, ）中的任意 a R，使得 na=0的最小正整数 n。若这样的 n不存在，则记环 R的特征为 0 练习：证明若R没有零因子，且特征不为0，那么特征一定为素数证明： 1）设特征为n=kl，其中k,l均g(b) 输出： gcd(a,b) 算法Init: i=0;r-1=a, r0=bDo: ri-2=qir
9、i-1+ri, i=i+1Until ri=0Return: ri-1其中 g(ri-1)g(ri)Euclid算法举例 求 gcd （ 84， 54）Z i=0;r-1=84, r0=54Z r-1=q1r0+r1=q1=1, r1=30Z r0=q2r1+r2=q2=1, r2=24Z r1=q3r2+r3=q3=1, r3=6Z r2=q4r3+r4=q4=4, r4=0Z 返回 r3=6=gcd(84,54)84 54A B一个简单记忆方法练习四，计算gcd(1970,1066)理解： qiri-1ri54 30130 24124 616 04扩展 Euclid算法 （回顾） gcd(
10、a,b)=sa+tb （最大公因子一定可以表达为 a， b的线性组合） MotivationZ 如果用 Euclid算法发现 gcd(a,b)=1，则有 1=sa+tbZ 既在 gcd(a,b)=1时找到了满足 b|1-sa的 sZ Euclid算法中 ri=ri-1-qiri-1,r-1=a ,r0=b=可以得到 a,b与 ri之间的递推关系 算法Z 定义序列 si ti,满足 s-1=1, s0=1, t-1=0, t0=1Z ti=ti-2-qiti-1; si=si-2-qisi-1Z ri=sia+tib for i=-1,0,n+1Z 算法终止于 rn+1=0, 返回 sn和 tn
11、扩展 Euclid算法举例a=84, b=54-1 1 0 84 -0 0 1 54 -1 1 -1 30 12 -1 2 24 13 2 -3 6 14 -9 14 0 4i sitiriqigcd(84, 54)=6=2 84+(-3) 54练习五，计算s,t,满足gcd(1970,1066) =s1970+t1066Euclid整环上的唯一分解Euclid整环（ E, +,， 0， 1） 引理 1： gcd(a,b)=1, 则存在 s,t E, sa+tb=1 引理 2： p是既约元， p|a，则 gcd(p,a)=1 引理 3：若 p为既约元， p|a，则存在 s,t E, sa+tp
12、=1 引理 4：若 p为既约元， p|ab,则 p|a或者 p|b(引理 1-4也适用于普通整环 ) 引理 5：在 Euclid整环中，若 a是 b的真因子，则有 g(a)1Euclid整环与域的关系Euclid整环（ D, +,， 0， 1） m E, m 0 定义等价关系， a,b E, a b iff m| a-b，记为 a b(mod m),.,)(mod.,/,/D,321321332132212111maaaamDDDDDDaDDDaDaDDaDaa=记记记记取jijijijiaaaaaaaa=+=+”：定义“”：定义“ 则当 m是既约元时 ）是域， 10,.,(321+maaaa
13、元素个数为素数 p的有限域 GF(p) 在所有 p阶域 F中，均至少存在一个 p-1阶元素g，称为 生成元 ，记 F*=g0,g1,gq-2, F*对是交换群。 Euler函数：(t)为0,1,2,t-1中与t互素的元素的个数 可以用扩展 Euclid算法计算 GF(p)中元素的逆元GF(pn) 定理：给定素数 p的幂 pn，一定存在阶为 pn的域，且该域在同构意义下是唯一的 下面通过介绍一类阶为 pn的域来理解 GF(pn)多项式环n次多项式 f(x)=a0+a1x+a2x2+anxn ai称为 (i=0,1,n)称为系数， a0称为常数项，若 an 0， an称为首项系数 n是 f(x)的次数，记为 deg f=n，如果 n=0,代表 f(x)为常量 若 ai环 R (i=0,1,n) ，则这样的多项式集合构成一个多项式环，其中00010() ; () ;() () ( )() ()nmiiiimniiii iiimnmkkkkijijkfx ax gx bx n mf xgx abx axfx gx cxcab=+=+=+= +=
