51一般单向函数 51.1单向函数的定义 定义51函数f:{}→{}*称为正则的,若存在正多项式 p(n)使对任一x∈901),有p((x)2。正则函数的含意是 f()的长不比x的长缩短太多。正则函数的一个重要的特殊 情形是保长函数,即对任一x∈{01}有f(x) 定义52一个函数f:{0,}→⑨0,}为强单向函数,若下列 两个条件成立: (1)计算f(x)是容易的,即fx)是多项式时间可计算的 参看定义4.10) (2)计算f(x)的逆f((x)是困难的,即对每一多项式时间 概率算法(参看定义4.13)M,每一正多项式p(η)和一切充 分大的m(mn≥n有 Pr{(f(n)∈f(U)}< p(n5.1 一般单向函数 ◼ 5.1.1 单向函数的定义 ◼ 定义 5.1 函数 称为正则的，若存在正多项式 p(n)使对任一 ，有 。正则函数的含意是 f(x)的长不比x的长缩短太多。正则函数的一个重要的特殊 情形是保长函数，即对任一 ，有 。 ◼ 定义 5.2 一个函数 称为强单向函数，若下列 两个条件成立： （1）计算f(x)是容易的，即f(x)是多项式时间可计算的 （参看定义4.10）； （2）计算f(x)的逆 是困难的，即对每一多项式时间 概率算法（参看定义4.13） ，每一正多项式p(n)和一切充 分大的 有 :0,1 0,1* * f →   * x  0,1 p( f (x))  x   * x  0,1 f (x) = x :0,1 0,1* * f → ( ( )) 1 f f x − ' M ( ) n n  n0   ( ) Pr ' ( ( )) 1 ( ( )) 1 p n M f Un  f f Un  −