第六章伪随机序列生成器 ●●●●● ●●●● ●●。●●
第六章 伪随机序列生成器
●●●●● ●●●● 6.1计算不可区分性 ●●0 ●●● ●●●● ●定义6.1一个概率分布族是由)一个无穷 子集l,称为指标集,和每个指标i∈对应一个 概率分布P(∞);D→01p(x)≥0∑P(x)=1构成,其中 x∈D D为)的一个有穷子集 ●定义62两个随机变量族{|x∈D,i∈l和y,ly∈E,iel 称为多项式时间不可区分,若对每个多项 式时间概率算法M,每个正多项式p(η)和一切 充分大的n有 P(x,)=1}-P{(C,)=l) (6.1)
6．1 计算不可区分性 ⚫ 定义 6.1 一个概率分布族是由 的一个无穷 子集I，称为指标集，和每个指标 对应一个 概率分布 构成，其中 Di为 的一个有穷子集。 ⚫ 定义 6.2 两个随机变量族 和 称为多项式时间不可区分，若对每个多项 式时间概率算法M’，每个正多项式p(n)和一切 充分大的n有 （6.1） * 0,1 i I → = Di x i i i i p (x): D [0,1], p (x) 0, p (x) 1 * 0,1 Xi | xi Di ,i I Yi | yi Ei ,i I ( ) Pr ' ( , ) 1 Pr ' ( , ) 1 1 p i M X i M Y i i = − i =
●●●●● ●●●● ●●0 ●●● ●●●● 定义6.3两个随机变量序列{x;n≥和{n;n≥} 的变差距离定义为 △(m)=∑Pr{n=x}-Pr{=xln21 (63) x∈0y ●定义6.4称一个随机变量序列{xn;n≥1是伪随机 的,若它与1}"上的均匀分布随机变量序列mn2l 是多项式时间不可区分的,其中设Xn取值于 0集
⚫ 定义 6.3 两个随机变量序列 和 的变差距离定义为 （6.3） ⚫ 定义 6.4 称一个随机变量序列 是伪随机 的，若它与 上的均匀分布随机变量序列 是多项式时间不可区分的，其中设Xn取值于 集。 Xn ;n 1 Yn ;n 1 = = − = n x n Xn x Yn x n 0,1 Pr Pr , 1 2 1 ( ) Xn ;n 1 ( ) 0,1 l n Ul(n) ;n 1 ( ) 0,1 l n
●●●●● ●●●● 62伪随机序列生成器的定义和性质 ●●0 ●●● ●●●● ●定义6.5一个伪随机序列生成器是一个确定性多项式 时间算法G满足下列两个条件: 1)延伸性,存在一个正整数函数m)>mn=12,…)使得对 切x∈{o}有G(x)=l(x); 2)伪随机性,随机变量序列G(U)n≥1}是伪随机的,即 它与均匀分布随机变量序列m;n21是多项式时间不 可区分的 生成器G的输入ⅹ称为它的种子,要求将长n比特的种 子延伸为长(n)比特的序列,且该序列与长(n)的随机 比特序列是多项式时间不可区分的。()>n称为的延 伸因子
6.2 伪随机序列生成器的定义和性质 ⚫ 定义 6.5 一个伪随机序列生成器是一个确定性多项式 时间算法G满足下列两个条件： 1)延伸性，存在一个正整数函数 使得对一 切 有 ； 2)伪随机性，随机变量序列 是伪随机的，即 它与均匀分布随机变量序列 是多项式时间不 可区分的。 生成器G的输入x称为它的种子，要求将长n比特的种 子延伸为长l(n)比特的序列，且该序列与长l(n)的随机 比特序列是多项式时间不可区分的。l(n)>n称为的延 伸因子。 l(n) n(n = 1,2, ) * x 0,1 G(x) = l( x ) G(Un );n 1 Ul(n) ;n 1
●●●●● 伪随机序列生成器的性质 ●●●● ●●0 (1)统计性质 ●●● ●●●● 定理61若是一个伪随机序列生成器,即满足定义 65中的条件,则随机变量序列{(Un)n≥1与{mn≥ 不是统计接近的。 (2)多项式延伸性 构造方法6.1,设G1为一确定性多项式时间算法,它 将每个长n比特串延伸为一个长n+1比特串,p(n)>n为 任一多项式。我们用G1作p(m)次迭代,即置s。=ss=n 为G1的初始输入,计算G(S)=x$,=1,2…,p(n),其中 x∈=-x为输入时G1输出的长n+1比特串 定义算法G为G()=x=xx2凝一个n长比特串s延 伸为一个p(n)长比特串x。由于G1是确定性多项式时 间算法,故G也是确定性的多项式时间算法
⚫ 伪随机序列生成器的性质 (1)统计性质 定理 6.1 若是一个伪随机序列生成器，即满足定义 6.5 中的条件，则随机变量序列 与 不是统计接近的。 (2)多项式延伸性 构造方法6.1，设G1为一确定性多项式时间算法，它 将每个长n比特串延伸为一个长n+1比特串，p(n)>n为 任一多项式。我们用G1作p(n)次迭代，即置 为G1的初始输入，计算 ，其中 即 为输入 时G1输出的长n+1比特串。 定义算法G为 ，它将一个n长比特串s延 伸为一个p(n)长比特串x。由于G1是确定性多项式时 间算法，故G也是确定性的多项式时间算法。 G(Un );n 1 Ul(n) ;n 1 s0 = s, s = n ( ) , 1,2, , ( ) G1 si−1 = xi si i = p n xi 0,1, si = si−1 = n i i x s i−1 s 1 2 ( ) ( ) p n G s = x = x x x