基本概念 单向函数:一个可逆函数f:A_B,若它满足: 10对所有x∈A,易于计算f(x)。 20对“几乎所有xA”由(x)求x“极为困难 ”,以至于实际上不可能做到,则称为一单 向( One-way)函数。 定义中的“易于计算”是指函数值能在其输 入长度的多项式时间内求出,即若输入长度 为n,计算函数的时间是na的倍数,a为一固 定的常数 若计算函数时间是a倍数,则为不可能做 到的。 2021-2-20 西大字2021-2-20 10