计算复杂性与抽象代数基础

第六讲计算复杂性与抽象代数基础

上海交通大学计算机系

龙宇

http://cis.sjtu.edu.cn/index.php/Yu_Long

内容

计算复杂性半群群子群环整环Euclid 整环有限域

问题与算法的复杂性

问题Q ：需要回答的一般性提问

Z该问题的全面描述和有关参量

Z陈述“解”必须满足的性质

问题的实例：将问题的所有参数赋值后所得的特例 问题的规模：或称输入长度，是为解决问题的实例所需输入变量的个数，或者输入二元数据的位数 算法：解决某问题Q 的一系列基本步骤或程序

算法复杂性及分类

算法复杂性：执行算法所花费的时间或空间代价：时间复杂度和空间复杂度

时间复杂性：简单的说，是解决问题Q 的任意实例所花费的最大值

算法复杂性T(n)是g(n)量级：指存在常数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 （n log n ）：亚指数时间

问题的复杂性及分类

问题的复杂性：简单的说，是解决问题的所有算法中复杂度最小值

P 问题：问题Q 可以用确定性图灵机在多项式时间内解决

NP 问题：问题Q 可以用非确定性图灵机在多项式时间内解决

NPC 问题：问题Q 是NP 的，且存在多项式时间内确定性算法能将任意NP 问题规约到该问题 P?=NP

计算复杂性与密码学的关系

单向函数(one way function)：

Z是函数f: AÆB ，f(x)=y

（P ）

（NP ）Z由任意x ∈A 求y 容易Z由“几乎所有”y求x 是极为困难的

陷门单向函数

Z由x 计算f(x)=y很容易（P ）

（NP ）

（P ）Z由y 计算x 很困难Z当某个陷门(trapdoor) k给定，由y, k计算x 容易

P ≠NP 是密码学的必要条件，但不是充分条件

一些概念

可忽略的量(negligible quantity)a function E (n ): NÆR is said to be a negligible quantity in n if its reciprocal is a non-polynomially-bounded quantity in 不可忽略的量: 1-E (n ) 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*，×) 单位元/逆元 无限群，abelian 群 Z*在×下不是群Z例3: n个元素的置换组成的集合，置换复合函数 群满足消去定律

a,b,c 属于群G ，则若ab=ac,有b=c

子群

定义

Z（G, ·）是群

ZH 是G 的非空子集

ZH 在·运算下仍是群

Z记做H ≤G

例: 在+运算下

（1）Z ≤Q ≤R ≤C

（2）{0,偶数} ≤Z

群的任意个子群的∩，仍然是群（子群） 但子群的∪一般不是子群

子集生成的子群

群/群元素的阶与循环群

群的阶Z有限群（G, ·）中，集合元素的个数，记为|G|群元素的阶Za ∈G,|a|为使a k =e的最小k, 记为|a|Za d =e, k|dH ≤G, 则一定有|H| | |G| (Lagrange定理）推论1：a ∈G ，则|a| | |G|, |a|代表a 的阶，也等于a 所生成子群的阶推论2；a ∈G, |a|=n, 则|ak |=n/(n,k)循环群

Z群（G, ·），a ∈G, ai =a·a·…·a; a0=e；a -n =(a-1) n

ZG=(a)={a0,a 1,…,an-1}，|G|=|a|

Z分类

无限循环群，阶为无穷大

有限循环群，n 阶，|a|=|(a)|=n

例：（Z, +）是无限循环群

环

定义：（R ，+, ×）

Z（R, +）是交换群（封闭、可结合、逆元、交换）Z（R, ×）是半群（封闭、可结合）Z×对+满足分配律

零元：+的单位元，记为0，任意a ∈R,0a=0 单位元：一般指×的单位元

交换环：指对×满足交换性

a ∈R, ka=a+a+…+a (k个a 相+） k a ∈R, a=a×a ×…×a (k个a 相×）

环举例

例1：整数、有理数、实数、复数对加法和乘法（数环）

例1：实数上n 阶方阵的集合对加法和乘法 例2：偶整数集合（正、负、0）对普通加法和乘法 例3：多项式环，设A 为数环

多项式集A[x]=a0+a1x+a2x 2+…+an x n

+ 定义为(a0,a 1,…)+(b0,b 1,…)=(a0+b0, a1+b1, …)×定义为(a0,a 1,…)×(b0,b 1,…)=(c0, c1,…)

c k =

i +j =k ∑a b i j

环的零因子与环的特征

对于环（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=k×l，其中k,l均

2）任意a ∈R，0=0a=(na)a=((k×l)a)×a=(ka)(la)

3）因为无零因子，所以ka=0或者la=0，与n为特征矛盾

4）n为素数

整环

定义（D, +,×，0，1）

Z是环

Z是交换环

Z含单位元：指乘法单位元，记为1Z不含零因子

Z对×满足交换性

整环举例

整数集合上的普通加法和乘法

注意：整环中并不要求存在乘法逆元

Euclid 整环和Euclid 算法

Euclid 整环定义（E, +,×，0，1）Z是整环

Z可以“比大小”：

任意a ∈E, 且a ≠0, 定义a 的大小为g(a), g(a)是非负整数 若b ≠0，有g(a) ≤g(ab)

Z任意a ，b ≠0，存在q ∈E ，r ∈E, 满足 a=qb+r（qb 代表q ×b ，下同）

r=0 或者g(r)

例1：（Z, +, ×，0，1）定义g(a)为取a 的绝对值|a|例2：有限整环上的多项式环(F[x], +, ×，0，1) ，定义g(f(x))为多项式的degree(f(x))

Euclid 整环上的一些定理

定理一：对E 上的b 1,b 2,…,bn ，若bi 不全为0，则存在k 1,k 2,…kn ∈E ，使得gcd （b 1,b 2,…,bn ）=k1b 1+…+kn b n 练习二：证明定理一

思路：定义集合S={k1b 1+…k n b n |ki ∈E}，则gcd=d，d∈S,且g(d)为最小。然后证明(1)d是公因子，(2)d是最大公因子 定理一的一个特例：n=2

对于E上的a ，b ，一定存在s,t ∈E ，使得gcd(a,b)=sa+tb 定理二：gcd （a,b ）=gcd(b,a)=gcd(b,a-qb),其中a,b,q ∈E 练习三：证明定理二

Euclid 算法与扩展Euclid 算法Euclid 算法

输入：a,b ∈E, 且a,b ≠0，不妨设 输出：gcd(a,b)

算法

Init:i=0;r-1=a, r0=b

Do:r i-2=qi r i-1+ri , i=i+1

Until r i =0

Return:r i-1

其中g(ri-1)>g(ri ) g(a)>g(b)

扩展Euclid 算法

（回顾）gcd(a,b)=sa+tb（最大公因子一定可以表达为a ，b 的线性组合）Motivation

Z如果用Euclid 算法发现gcd(a,b)=1，则有1=sa+tbZ既在gcd(a,b)=1时找到了满足b|1-sa的s

ZEuclid 算法中r i =ri-1-q i r i-1,r -1=a ,r0=b=>可以得到a,b 与r i 之间的递推关系

算法

Z定义序列{si} {ti},满足{s-1=1, s0=1}, {t-1=0, t0=1}Zt i =ti-2-q i t i-1; si =si-2-q i s i-1Zr i =si a+ti b

for i=-1,0,…,n+1

Z算法终止于r n+1=0, 返回s n 和t n

Euclid 整环上的唯一分解定理

设b ∈E, b不是零元，b 不等价于1，则有：

b 可以分解为有限个既约元之乘积；b=p1p 2…pr 若b 有另一分解式b=q1q 2…qs ，则经过适当排序后，

有p i ～q i ，s=r

证明思路：对g(b)进行数学归纳证明（略）

域与有限域

定义：（F ，+, ×，0，1）Z是整环

Z所有非零元都有乘法逆元

可以简单记忆为:F对+和×运算都是Abelian 群（乘法群为F/{0}），各自的单位元分别为0和1，，且×对+满足分配律优点：a+x=b 和cx=d（c ≠0）均有解且为唯一解

子域：H 是F 的子集，若（H, +, ×，0，1）仍然是域，称为F 的子域素域：不含有子域的域

分类（按照子域同构，仅可以划分为两类）

Z有限域：F 中元素个数有限，特征一定为某素数p ，F 含同构于Z p 的素域

Z无限域：F 中元素个数无限，特征为0，F 含有同构于有理数域的素域例：有理数、实数、复数集合均是域（无限域），整数集合对普通乘法和加法不是域

有限域

特征为素数p 的域称为有限域，有限域在密码

学算法中扮演着非常重要的角色

另一种说法：元素个数有限，且个数一定为

一个素数p 的幂。因此，一个元素个数为pq…(p≠q) 的集合一定不能构成域

n 记为GF （p ）：Galois field

分类

Zn=1Zn>1

元素个数为素数p 的有限域GF(p)

在所有p 阶域F 中，均至少存在一个p-1阶元素

g ，称为生成元，记F*={g0,g 1,…,gq-2}, F*对×是交换群。

Euler 函数：Φ(t)为{0,1,2,…,t-1}中与t互

素的元素的个数

可以用扩展Euclid 算法计算GF(p)中元素的逆

元

n GF(p)

n n 定理：给定素数p 的幂p ，一定存在阶为p 的

域，且该域在同构意义下是唯一的

n n 下面通过介绍一类阶为p 的域来理解GF(p)

多项式环

n 次多项式f(x)=a0+a1x+a2x 2…+an x n

a i 称为(i=0,1,…,n)称为系数，a 0称为常数项，若a n ≠0，a n 称为首项系数

n 是f(x)的次数，记为deg f=n，如果n=0,代表f(x)为常量若a i ∈环R (i=0,1,…,n) ，则这样的多项式集合构成一个多项式环，其中

f (x ) = ∑n

a i x ; i g (x ) =

i =0∑b x i i =0m i ; n ≥m

(a i +b i ) x i +

c k x k 加法定义为：f (x ) +g (x ) =乘法定义为：f (x ) ×g (x ) =

c k =∑∑m i =0i =m +1∑n a i x i n +m k =0

i +j =k ∑a i b j

上面的多项式环记为R(x)

R(x)对于乘法的逆运算不是总有定义的Z 例：n=2，R为整数环，5x2,3x∈R[x],但是5/3在R上无定义, 5x2/3x在R[x]上也没有定义 R(x)是环不是域

将r(x)记为f(x) mod g(x)

Z如果r(x)=0, 称g(x)整除f(x),记为g(x) | f(x)

Zg(x)称为f(x)的一个因式

既约多项式：域F 上的多项式f(x)，deg f(x) ≥1是不可约的，是指若存在g(x) ∈F(x)，g(x) | f(x) 则

Z

Zdeg g(x)=0deg g(x)=deg f(x)

例：F 2(x)，

f(x)=x3+x+1是既约多项式（如何证明？）f(x)=x4+1=(x+1)(x3+x2+x+1)不是既约多项式

F(x)上的最大公因式及计算方法 a(x),b(x) ∈F(x), 如果c(x)|a(x), c(x)|b(x) 任意d(x)|a(x),e(x)|b(x), 均有d(x)|c(x), e(x)|c(x)

c(x)称为a(x),b(x) 的最大公因式，记为gcd[a(x), b(x)]=c(x)

可以用Euclid 算法有效计算出c(x) 可以用扩展Euclid 算法计算出

c(x)=s(x)a(x)+t(x)b(x)

33例：选择既约多项式x +x+1∈GF(2)

∈加法表

乘法表

AES

举例

总结知识要点 群的定义，生成元 环与整环的定义 域的定义，域的生成元，域的分类 用Euclid 算法计算两个整数的最大公因子 用扩展Euclid 算法计算乘法逆元

谢谢!