伪随机序列生成器.ppt
第六章第六章 伪随机序列生成器伪随机序列生成器61 计算不可区分性计算不可区分性 l定义 6.1 一个概率分布族是由 的一个无穷子集I，称为指标集，和每个指标 对应一个概率分布 构成，其中Di为 的一个有穷子集。l定义 6.2 两个随机变量族 和称为多项式时间不可区分，若对每个多项式时间概率算法M，每个正多项式p(n)和一切充分大的n有 （6.1）l定义 6.3 两个随机变量序列 和 的变差距离定义为 （6.3）l定义 6.4 称一个随机变量序列是伪随机的，若它与 上的均匀分布随机变量序列是多项式时间不可区分的，其中设Xn取值于 集。6.2 伪随机序列生成器的定义和性质伪随机序列生成器的定义和性质 l定义 6.5 一个伪随机序列生成器是一个确定性多项式时间算法G满足下列两个条件：1)延伸性，存在一个正整数函数 使得对一切 有 ；2)伪随机性，随机变量序列是伪随机的，即它与均匀分布随机变量序列 是多项式时间不可区分的。生成器G的输入x称为它的种子，要求将长n比特的种子延伸为长l(n)比特的序列，且该序列与长l(n)的随机比特序列是多项式时间不可区分的。l(n)n称为的延伸因子。l伪随机序列生成器的性质(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也是确定性的多项式时间算法。(3)不可预测性。定义 6.6 随机变量序列 称为多项式时间不可预测的若对每个多项式时间概率算法M，每个正多项式p(n)和一切充分大的n有 （6.4）定理 6.3 一个随机变量序列 是伪随机的（参看定义6.4）当且仅当它是多项式时间不可预测的。(4)单向函数性。定理 6.4 设G为一延伸因子l(n)的伪随机序列生成器，若对每对 满足 ，定义函数，则f为一强单向函数。63 伪随机序列生成器的构造伪随机序列生成器的构造 6.3.1 用一般单向置换构造伪随机序列生成器 定理 6.5 设 为一11保长强单向函数，为函数f的硬核谓词（多项式时间可计算）。定义 （b(x)和f(x)的连接），则G为一伪随机序列生成器。632 用单向置换族构造伪随机序列生成器 定理 6.6 设多项式时间概率算法A,D,F定义一单向置换族，为该单向置换族的硬核谓词族，q(n)及，G如构造方法6.2中所给。再设对每个 ，D(i)为在Di上均匀分布的随机变量，则G为一伪随机序列生成器，它将2q(n)长的种子(r,s)延伸为p(n)长的伪随机序列。6.4 用伪随机序列生成器构造伪随机函数用伪随机序列生成器构造伪随机函数 l定义 6.7 一个随机函数序列是一个在函数集 中取值的随机变量序列，其概率分布为 ，即 ，特别地，一个随机函数序列称为真随机函数序列若其概率分布为 上的均匀分布，即对每个 有，记真随机函数序列为。l定义 6.8一个确定性神图灵机是一个确定性图灵机（见定义4.4）附加一条磁带，称为神带，和两个特殊状态，sinv称为求神状态，sora称为神现状态。当一个神图灵机M输入x，存取函数时，其计算也是一个形的有限或无限序列，其关系由读写头所处状态的转移函数和读写头动作的指令函数确定，若，则第j+1个形如定义4.4所给，若第j个形中的状态sj=sinv，且神带中的内容为 ，则第j+1个形中的状态sj+1=sora，且神带中的内容为f(q)，q称为M的提问，f(q)称为神的回答。神图灵机的输出M，记作Mf(x)，以及运行（计算）时间如定义4.4所定义。l定义 6.9 一个随机函数序列 称为伪随机函数序列若对每个多项式时间神概率图灵机M，每个正多项式p(n)和一切充分大的n有 （6.5）l构造方法6.3，设G为一个确定性算法，它将n长比特串s延伸为2n长比特串G(s)，定义函数G0(s)为G(s)的前n个比特，G1(s)为G(s)的后n个比特（即G(s)=G0(s)G1(s)）对每个 和每个 ，定义函数 (6.6)定义随机函数 ，其中Un为 上的均匀分布随机变量（即s在 中按均匀分布随机抽取），即为所构造的随机函数序列。65 伪随机置换的构造伪随机置换的构造 l定义 6.10 一个随机置换序列 是一个在置换集 中取值的随机变量序列，其概率分布为，即 ，特别地，一个随机置换序列称为真随机置换序列，若其概率分布为 上的均匀分布，即对每个 有，记真随机置换序列为 。l定义 6.11 一个随机置换序列称为伪随机置换序列，若对每个多项式时间神概率图灵机M，每个正多项式p(n)和一切充分大的n有（6.7）l定理 6.8 设Fn，t(n)，如构造方法6.4中所给。若随机函数序列 是多项式时间可实现（计算）的，且t(n)是多项式时间可计算的，则随机函数序列 也是多项式时间可实现的，且为多项式时间可逆的随机置换序列，更进一步，若 是一个伪随机函数序列，则 为一伪随机置换序列。
