5.3单向函数族的其它性质 ■53.1单向陷门置换族 定义56设:D→D;∈为一单向置换族。由定义 5.5及其后的说明知,存在多项式时间概率算法A 和D及多项式时间确定性算法F满足定义5.5中的 条件1)和2)(参看定义55) 单向置换族:D→D;∈称为单向陷门置换族,若 存在一个多项式时间概率算法A1→0×}和 个多项式时间确定性算法F满足如下条件,其中 n=1,2,… ■3)4(1)=(4(1"),z(A()=(n,(n),其中A"和A(")分别 表示算法A和A输入1时的输出,1为1⌒上的随机 变量,且对每对(,(),i∈l 和x∈D每个有F(xo()=x 即陷门作为求逆算法的辅助输入。5．3 单向函数族的其它性质 ◼ 5.3.1 单向陷门置换族 ◼ 定义5.6 设 为一单向置换族。由定义 5.5 及其后的说明知，存在多项式时间概率算法 和D及多项式时间确定性算法F满足定义5.5中的 条件1）和2）（参看定义5.5）。 ◼ 单向置换族 称为单向陷门置换族，若 存在一个多项式时间概率算法 和一 个多项式时间确定性算法 满足如下条件，其中 。 ◼ 3） ，其中 和 分别 表示算法A和 输入 时的输出，为 上的随机 变量，且对每对 和 每个有 ， 即陷门 作为求逆算法 的辅助输入。 f i : Di → Di ;i  I A1 f i : Di → Di ;i  I     * * * A:1 → 0,1  0,1 −1 F 1 1 ; 1,2,  * = n = n (1 ) ( (1 ), ( (1 )) ( , ( )) 1 1 n n n n n A = A  A = I  I (1 ) n A (1 ) 1 n A A1 n 1 n I   n I  0,1 (i, (i)),i  I Di x  F i f x x i = − ( ( ), ( )) 1   (i) −1 F