单向函数举例(续) 2.因数分解问题 Factorization prob|em 给定大素数p和q,求n=p×q,只要一次乘法 给定n,求p和q,即为因数分解问题(FAC,最快方法需要 T(n)=exp{c(nnn(nn)号次运算,其中C为大于 的正整数。 3.背包问题 Knapsack problem 给定有限个自然数序列集合B=(b1,b2,b)及二进制序列 =(X1,x2,Xn),X∈(0,1),求S=∑Xb最多只需n-1次 加法;但若给定B和S,求x则非常困难。 穷举时有2种可能,当n很大时为计算上不可行。 Garey和 Johnson证明,背包问题是NP问题 (Non-Polynomial) ash mfy@ustc.edu.cn 现代密码学理论与实践 12/81mfy@ustc.edu.cn 现代密码学理论与实践 12/81 2. 因数分解问题Factorization Problem 给定大素数 p和q, 求n = p×q, 只要一次乘法 给定n, 求p和q, 即为因数分解问题(FAC), 最快方法需要 T(n) = exp {c(ln n ln (ln n))½ } 次运算, 其中c为大于 1的正整数。 3. 背包问题Knapsack Problem 给定有限个自然数序列集合B=(b1 ,b2 ,…bn )及二进制序列 x=(x1 ,x2 ,…xn ), xi∈(0,1), 求S=∑xibi最多只需n-1次 加法；但若给定B和S, 求x则非常困难。 穷举时有2n种可能, 当n很大时为计算上不可行。 Garey和Johnson证明, 背包问题是NP问题 (Non-Polynomial)