Question

单向函数的单向函数定义

Answer 1

一函数f若满足下列二条件，则f称为单向函数：
① 对于所有属于 f 定义域的任一 x ，可以很容易计算 f( x ) = y；
②对于几乎所有（Almost All）属于 f 值域的任一 y ，则在计算上不可能（Computationally Infeasible）求出 x 使得 y = f( x )；
单向函数的例子：
1、令 f 为一 n 阶多项式，且 y = f( x ) = x^n + a[n-1] x^(n-1) + … + a[1]x + a[0] mod p。给出a[0]，a[1]， …，a[n-1]，p 及x，欲求 y ，只需最多n个乘法及n-1个加法。因为 y = f( x) = (...(x + a[n-1]) x + a[n-2])x + a[n-3]) x + ... +a[1]) x + a[0] mod p。此即为有名的Honer's Rule。但若已给a[0]，a[1]， …，a[n-1]及y，欲求出 f( x )的 x，则至少需要n^2((log[2]p)^2)次乘法，当n及p很大时，可知由y求x，比由x求y难上许多。
2、求离散对数问题（Discrete Logarithm Problem, DLP )
令素数p满足p-1含有另一大素因子q（即q整除p-1）及一整数g，1<g<p-1。已给一整数x，欲求y = g^x mod p，最多只需要『log[2]x』+ w(x) - 1个乘法。其中『a』表示高斯符号，即比a小的最大整数。如a = 3.14，则『a』= 3。w( x) 表示x用二进制表示法中所有1的个数。例如 x=15=1111[2]，则g^15=(((1*g)^2*g)^2*g)^2*g mod p。只需要3+4-1=6次乘法。但若已给p，g 及y 欲求x ，此问题称为求离散对数问题。现今已知最快的方法需要L（p）=exp(ln p (ln( ln p ))^(1/2))次运算。求离散对数为几千年来数学界一直无法突破的难题。当 p = 512时，L(p)约为2^256≈ 10^77。欲由y求出x,则为计算机上不可能。
此外，还有很多单向函数的数学问题，例如因子分解问题，背包问题等，在此无法一列举。