第 4章 密码学的计算复杂性
理论基础
4.1 问题与算法的复杂性
? 4.1.1 问题与语言
– 例 4.1, 整数的因子分解问题。
– 例 4.2, 背包问题。
实际应用中的绝大多数问题都可直接或
间接地转化为判定问题。
? 定义 4.1 的任一子集 L称为一个 B－语言（或
简称语言）。语言 L中的字称为语言 L的成员。
? 定义 4.2 设一个语言 已给定。语言 L成员
的识别问题可描述为：任给 （参数），问
是否 x是 L语言的成员（是否 ）？
? 定义 4.3 设 为一个问题,B为一个字符
集。从 I到 中的一个映射 c，满足条件
（空集），称为问题 D的一个 B－编码。若 c为
D的一个编码，集 称为
D的一个 c－语言。
*B
*BL?
*Bx?
Lx?
),( ?? IID
*B ??? ?? )()( IcIc
? ? )();(),( ?? ??? IcIccDL ??
? 引理 4.1 若 c为 D的一个编码，则求解问题 D和
求解语言 的成员识别问题是等价的，即
问题 D的任一例子,其答案与语言 的
成员识别问题的例子的答案 是相同的。
? 一个合理编码还应满足下列两个基本要求,
1） 编码是容易实现的；
2） 求解问题的任一例子的计算复杂性（通常
用计算时间来表示）与的长有某种正比关系。
),( cDL
I?? ),( cDL
)(?c
4.1.2 算法与图灵机
…, -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 … 无限长
磁带
有限状态控制器
读写头
图 4.1 确定性单带图灵机示意图
? 定义 4.4 一个确定性单带图灵机由下列集和函数构成。
1,1）带中所用字符集 B，通常可设,其中 表示空。
2）读写头所处的可能状态集 S，其中包含一个初始状态
和若干个停机状态 。
3）读写头所处状态的转移函数,它是读写头现在所处状
态 s和所读字符 b的函数，表示为 。
4）读写头动作的指令函数,它也是读写头现在所处状态 s
和所读字符 b的函数，表示为,其中
且都不属于 B。若,则读写头写字符 代替 b，
且保持原位不动。若,则原字符 b保持不变，
读写头向左（或向右）移动一个小方格。
2,磁带上的每个小方格用一个整数坐标 i表示。小方格 i中的字
符记作 t(i)，磁带表示为函数 。
? ??,1,0?B ?
0s
ST?
?
SBS ??:?
?
? ?rlBBS,,???? rl?
Bbbs ?? '),(? 'b
)(),( rlbs 或??
BZt ?整数集）(:
3,图灵机在某一时刻的形是指一个三元组,它们分
别表示该时刻读写头所处状态，磁带和读写头所扫描的
小方格坐标,t(i)为读写头在该时刻所读字符。
4,一个图灵机的计算程序（算法）是一个形的有限或无限
序列,其中 为图灵机在初
始时刻的形，即 为初始状态，为初始磁带，它由输入
数据（字） 给出，通常存放在 小方格中，其
它小方格中为空字符,通常 。图灵机在 k时刻的
形 由下面的递推式给出。
若存在形 使,则计算在时刻
终止，同时停机，称 或 为计算的输出结果,K
称为图灵机（算法）的运行（计算）时间。否则计算将
不终止，不停机，直到无限。
),,( its
?),,,(),,,(),,,( 222111000 itsitsits ),,( 000 its
0s 0t
*Bx? x?1
? 1
0 ?i
?,2,1),,,( ?kits kkk
))(,( 111 ???? kkkk itss ?
?
?
?
?
??
?
?
?
????
????
?
?
?
?
?
?
???
?????
?????
??
?
????
1,))(,(
1,))(,(
)3.4(
)(
)(
))(,(
11111
11111
11
1
1111
kkkkkkk
kkkkkkk
kk
k
k
kkkkk
iittrits
iittlits
iiit
iib
it
iiBbits
则若
则若
则若
?
?
?
),,( kkk its Tsk ? );m in ( TskK k ??
),( kk it )(kk it
? 定义 4.5 称一个图灵机 M可解一个语言
L 的成员识别问题,若对任一输入数
据, M在有限时刻 停机，且 M
的输出,若 。否则 。
图灵机的计算复杂性定义为
? 定义 4.6 设 f(n)和 g(n)为两个正整数函数，
若存在正整数 和常数 c使当 时
有,则记作 ；
若,,则记作
? ?*1,0?x )(xK
1)( )()( ?xKxK it Lx? 0)( )()( ?xKxK it
? ?)(m a x)( ; xKnf nxxM ??
0n 0nn?
)()( ncgnf ? ))(()( ngnf ??
))(()( ngnf ?? ))(()( nfng ??
))()( ngnf Θ （?
? 定义 4.7 设 和 为图灵机 M和 的
计算复杂性，若,则称算法
不比算法 M有效；若,则称算
法 M和 是等效的；若存在正整数 d,
,则称 M为多项式时间算法，按
密码学中的传统观念，认为多项式时间
算法为有效算法；若,则称 M
为亚指数时间算法；若,
则称 M为指数时间算法。亚指数和指数
时间算法也被称为超多项式时间算法，
被认为不是有效算法。
)(nfM )(' nfM 'M
))(()( ' nfnf MM ?? 'M
))(()( ' nfnf MM ??
'M
)()( dM nnf ??
)2()( l o g nM nf ??
)10)2()( nnM nf （或 ???
4,2 问题的计算复杂性分类
? 4.2.1 P,NP,NP完全类问题
? 定义 4.8 一个语言 L的成员识别问题属于 P类，若存在
一个可解该问题的图灵机 M和一个正多项式,使
M的计算复杂性,所有 P类问题构成
的集记作 P。
? 定义 4.9 一个语言 L的成员识别问题属于 NP类，若存
在一个 的子集 （称为一个布尔关系）
及一个正多项式 p(n)满足下列两个条件,
1） 的成员识别问题属于 P类；
2） 当且仅当存在一个 y，其长,且 。
这样的 y称为是 的证据。所有 NP类问题构成的集
记作 NP。
)(np
))(()( npnf M ??
? ? ? ?** 1,01,0 ? ? ?),( yxR L ?
LR
Lx? )( xpy ? LRyx ?),(
Lx?
? 定义 4.9 一个语言的成员识别问题属于
NP类，若存在一个的子集（称为一个布
尔关系）及一个正多项式 (n)满足下列两
个条件,
1）的成员识别问题属于 P类；
2）当且仅当存在一个，其长，且。这样
的称为是的证据。所有 NP类问题构成的
集记作 NP。
? 定义 4.10 称一个图灵机 M可计算一个函
数,若对任一输入数据,
M在有限时刻 停机，且 M的输出磁带 上的
二进数序列（不包含空 ） 。若 M是多
项式时间算法，则称 f(x)是多项式时间可计算
的。
? 定义 4.11 一个语言 L称为可多项式时间化为另
一语言,若存在一个多项式时间可计算函数
f(x)，使 当且仅当,这时也称语言 L的
成员识别问题可多项式时间化为语言 的成员
识别问题。
? 定义 4.12 一个语言 L的成员识别问题属于 NP
完全 (NPC)类，若它属于 NP类，且每个 NP类
语言成员识别问题都可多项式时间化为语言 L
的成员识别问题。所有 NP完全类问题构成的
集记作 NPC。
? ? ? ?** 1,01,0:)( ?xf ? ?*1,0?x
)(xK )(xKt
? )()( xfxM ?
'L
Lx? ')( Lxf ?
'L
4.2.2 概率算法与 BPP类问题
? 概率算法就是在执行计算的过程中允许
用随机数。
? 定义 4.13 一个概率算法（图灵机）称为
多项式时间概率算法。若存在一个多项
式 p(n)，对任一,有 。
换句话说，对所有扔硬币结果 r（可
设 ）都有 。
? ?*1,0?x ? ? 1)()(Pr ?? xpxK
)( xpr ? )()( xpxK r ?
? 定义 4.14 称一个多项式时间概率算法 M可解
一个语言 L的成员识别问题，若对任一输入数
据,有
（ 1）若,则
（ 2）若,则
称一个语言 L的成员识别问题属于 BPP类，若
存在一个可解该问题的多项式时间概率算法。
所有 BPP类问题构成的集记作 BPP。
? ?*1,0?x
Lx?
Lx?
? ? 3/21)(Pr ??xb
? ? 3/20)(Pr ??xb
小结
? 计算复杂性理论是现代密码学的理论基础。
? 关于算法的时间复杂性有两种定义方法：一是
用一个图灵机表示一个算法，该算法的时间复
杂性定义为该图灵机运行的步数；二是定义一
个算法的时间复杂性为该算法的比特运算次数。本章使用前者。
? 关于判定问题到语言成员识别问题的合理编码，
关于估计算法的比特运算次数的方法，关于
NP完全问题。
理论基础
4.1 问题与算法的复杂性
? 4.1.1 问题与语言
– 例 4.1, 整数的因子分解问题。
– 例 4.2, 背包问题。
实际应用中的绝大多数问题都可直接或
间接地转化为判定问题。
? 定义 4.1 的任一子集 L称为一个 B－语言（或
简称语言）。语言 L中的字称为语言 L的成员。
? 定义 4.2 设一个语言 已给定。语言 L成员
的识别问题可描述为：任给 （参数），问
是否 x是 L语言的成员（是否 ）？
? 定义 4.3 设 为一个问题,B为一个字符
集。从 I到 中的一个映射 c，满足条件
（空集），称为问题 D的一个 B－编码。若 c为
D的一个编码，集 称为
D的一个 c－语言。
*B
*BL?
*Bx?
Lx?
),( ?? IID
*B ??? ?? )()( IcIc
? ? )();(),( ?? ??? IcIccDL ??
? 引理 4.1 若 c为 D的一个编码，则求解问题 D和
求解语言 的成员识别问题是等价的，即
问题 D的任一例子,其答案与语言 的
成员识别问题的例子的答案 是相同的。
? 一个合理编码还应满足下列两个基本要求,
1） 编码是容易实现的；
2） 求解问题的任一例子的计算复杂性（通常
用计算时间来表示）与的长有某种正比关系。
),( cDL
I?? ),( cDL
)(?c
4.1.2 算法与图灵机
…, -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 … 无限长
磁带
有限状态控制器
读写头
图 4.1 确定性单带图灵机示意图
? 定义 4.4 一个确定性单带图灵机由下列集和函数构成。
1,1）带中所用字符集 B，通常可设,其中 表示空。
2）读写头所处的可能状态集 S，其中包含一个初始状态
和若干个停机状态 。
3）读写头所处状态的转移函数,它是读写头现在所处状
态 s和所读字符 b的函数，表示为 。
4）读写头动作的指令函数,它也是读写头现在所处状态 s
和所读字符 b的函数，表示为,其中
且都不属于 B。若,则读写头写字符 代替 b，
且保持原位不动。若,则原字符 b保持不变，
读写头向左（或向右）移动一个小方格。
2,磁带上的每个小方格用一个整数坐标 i表示。小方格 i中的字
符记作 t(i)，磁带表示为函数 。
? ??,1,0?B ?
0s
ST?
?
SBS ??:?
?
? ?rlBBS,,???? rl?
Bbbs ?? '),(? 'b
)(),( rlbs 或??
BZt ?整数集）(:
3,图灵机在某一时刻的形是指一个三元组,它们分
别表示该时刻读写头所处状态，磁带和读写头所扫描的
小方格坐标,t(i)为读写头在该时刻所读字符。
4,一个图灵机的计算程序（算法）是一个形的有限或无限
序列,其中 为图灵机在初
始时刻的形，即 为初始状态，为初始磁带，它由输入
数据（字） 给出，通常存放在 小方格中，其
它小方格中为空字符,通常 。图灵机在 k时刻的
形 由下面的递推式给出。
若存在形 使,则计算在时刻
终止，同时停机，称 或 为计算的输出结果,K
称为图灵机（算法）的运行（计算）时间。否则计算将
不终止，不停机，直到无限。
),,( its
?),,,(),,,(),,,( 222111000 itsitsits ),,( 000 its
0s 0t
*Bx? x?1
? 1
0 ?i
?,2,1),,,( ?kits kkk
))(,( 111 ???? kkkk itss ?
?
?
?
?
??
?
?
?
????
????
?
?
?
?
?
?
???
?????
?????
??
?
????
1,))(,(
1,))(,(
)3.4(
)(
)(
))(,(
11111
11111
11
1
1111
kkkkkkk
kkkkkkk
kk
k
k
kkkkk
iittrits
iittlits
iiit
iib
it
iiBbits
则若
则若
则若
?
?
?
),,( kkk its Tsk ? );m in ( TskK k ??
),( kk it )(kk it
? 定义 4.5 称一个图灵机 M可解一个语言
L 的成员识别问题,若对任一输入数
据, M在有限时刻 停机，且 M
的输出,若 。否则 。
图灵机的计算复杂性定义为
? 定义 4.6 设 f(n)和 g(n)为两个正整数函数，
若存在正整数 和常数 c使当 时
有,则记作 ；
若,,则记作
? ?*1,0?x )(xK
1)( )()( ?xKxK it Lx? 0)( )()( ?xKxK it
? ?)(m a x)( ; xKnf nxxM ??
0n 0nn?
)()( ncgnf ? ))(()( ngnf ??
))(()( ngnf ?? ))(()( nfng ??
))()( ngnf Θ （?
? 定义 4.7 设 和 为图灵机 M和 的
计算复杂性，若,则称算法
不比算法 M有效；若,则称算
法 M和 是等效的；若存在正整数 d,
,则称 M为多项式时间算法，按
密码学中的传统观念，认为多项式时间
算法为有效算法；若,则称 M
为亚指数时间算法；若,
则称 M为指数时间算法。亚指数和指数
时间算法也被称为超多项式时间算法，
被认为不是有效算法。
)(nfM )(' nfM 'M
))(()( ' nfnf MM ?? 'M
))(()( ' nfnf MM ??
'M
)()( dM nnf ??
)2()( l o g nM nf ??
)10)2()( nnM nf （或 ???
4,2 问题的计算复杂性分类
? 4.2.1 P,NP,NP完全类问题
? 定义 4.8 一个语言 L的成员识别问题属于 P类，若存在
一个可解该问题的图灵机 M和一个正多项式,使
M的计算复杂性,所有 P类问题构成
的集记作 P。
? 定义 4.9 一个语言 L的成员识别问题属于 NP类，若存
在一个 的子集 （称为一个布尔关系）
及一个正多项式 p(n)满足下列两个条件,
1） 的成员识别问题属于 P类；
2） 当且仅当存在一个 y，其长,且 。
这样的 y称为是 的证据。所有 NP类问题构成的集
记作 NP。
)(np
))(()( npnf M ??
? ? ? ?** 1,01,0 ? ? ?),( yxR L ?
LR
Lx? )( xpy ? LRyx ?),(
Lx?
? 定义 4.9 一个语言的成员识别问题属于
NP类，若存在一个的子集（称为一个布
尔关系）及一个正多项式 (n)满足下列两
个条件,
1）的成员识别问题属于 P类；
2）当且仅当存在一个，其长，且。这样
的称为是的证据。所有 NP类问题构成的
集记作 NP。
? 定义 4.10 称一个图灵机 M可计算一个函
数,若对任一输入数据,
M在有限时刻 停机，且 M的输出磁带 上的
二进数序列（不包含空 ） 。若 M是多
项式时间算法，则称 f(x)是多项式时间可计算
的。
? 定义 4.11 一个语言 L称为可多项式时间化为另
一语言,若存在一个多项式时间可计算函数
f(x)，使 当且仅当,这时也称语言 L的
成员识别问题可多项式时间化为语言 的成员
识别问题。
? 定义 4.12 一个语言 L的成员识别问题属于 NP
完全 (NPC)类，若它属于 NP类，且每个 NP类
语言成员识别问题都可多项式时间化为语言 L
的成员识别问题。所有 NP完全类问题构成的
集记作 NPC。
? ? ? ?** 1,01,0:)( ?xf ? ?*1,0?x
)(xK )(xKt
? )()( xfxM ?
'L
Lx? ')( Lxf ?
'L
4.2.2 概率算法与 BPP类问题
? 概率算法就是在执行计算的过程中允许
用随机数。
? 定义 4.13 一个概率算法（图灵机）称为
多项式时间概率算法。若存在一个多项
式 p(n)，对任一,有 。
换句话说，对所有扔硬币结果 r（可
设 ）都有 。
? ?*1,0?x ? ? 1)()(Pr ?? xpxK
)( xpr ? )()( xpxK r ?
? 定义 4.14 称一个多项式时间概率算法 M可解
一个语言 L的成员识别问题，若对任一输入数
据,有
（ 1）若,则
（ 2）若,则
称一个语言 L的成员识别问题属于 BPP类，若
存在一个可解该问题的多项式时间概率算法。
所有 BPP类问题构成的集记作 BPP。
? ?*1,0?x
Lx?
Lx?
? ? 3/21)(Pr ??xb
? ? 3/20)(Pr ??xb
小结
? 计算复杂性理论是现代密码学的理论基础。
? 关于算法的时间复杂性有两种定义方法：一是
用一个图灵机表示一个算法，该算法的时间复
杂性定义为该图灵机运行的步数；二是定义一
个算法的时间复杂性为该算法的比特运算次数。本章使用前者。
? 关于判定问题到语言成员识别问题的合理编码，
关于估计算法的比特运算次数的方法，关于
NP完全问题。
