合数的素因子分解 任一给定的正整数,可通过简单列出所有后面公式中 非零指数分量来说明 ■ EX:12可以表示为{a2=2,a3=13,18可以表示为 {a2=1,a3=2},91可以表示为{a7=1,a13=1 两个数的乘法等同于对应指数分量的加法 k=m→k=m+n对所有p Ex:k=12X18=(22×3)X(2X32)=216,k2=2+1=3, 1+2 3,∴216=23×3 任何以p形式表示的整数仅能被对应素数分量小于 或等于它的另一个整数p整除,其中/k,即有叫b a≤b,对所有素数成立 Ex:a=12,b=36,12|36,12=22X31,36=22×32 2=b2 ≤2=b3 ash mfy@ustc.edu.cn 现代密码学理论与实践 /81
mfy@ustc.edu.cn 现代密码学理论与实践 8/81 任一给定的正整数, 可通过简单列出所有后面公式中 非零指数分量来说明. Ex：12可以表示为{a2=2, a3=1}, 18可以表示为 {a2=1, a3=2}, 91可以表示为{a7=1, a13=1} 两个数的乘法等同于对应指数分量的加法 k=mn →kp = mp + np 对所有p Ex：k=12x18=(22x3)x(2x32 )=216, k2=2+1=3, k3=1+2=3, ∴ 216=23x33 任何以pk形式表示的整数仅能被对应素数分量小于 或等于它的另一个整数pj 整除, 其中j≤k，即有a|b →ap≤bp ，对所有素数p成立。 Ex：a=12, b=36, 12|36, 12=22x31 , 36=22x32 a2=2=b2 , a3=1≤2=b3
互素和最大公约数GCD gcd(a,b)=C,即c是a和b的最大公约数,当 C是a和b的因子 2任何a和b的因子也是c的因子 两个整数a,b,如果除了1以外没有公共因子,则称它们互 素( Relatively prime 8和15互素,因为8的因子是12,4,8,而15的因子是 它们唯一的公共因子。 〉如果将整数表示为素数之积,则容易确定两个正整数的最 公因子 下列关系总是成立的 如果k=gcd(a,b),则k=min(amb,对于任意的∈P 例子: 300=22x3l×52,18=2lX32 gcd(18,300)=2x3×50=6 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 9/81
mfy@ustc.edu.cn 现代密码学理论与实践 9/81 gcd(a, b)=c, 即c是a和b的最大公约数, 当 1.c是a和b的因子 2.任何a和b的因子也是c的因子 两个整数 a, b, 如果除了1以外没有公共因子, 则称它们互 素(Relatively Prime) 8和15互素, 因为8的因子是1,2,4,8, 而15的因子是 1,3,5,15, 1是它们唯一的公共因子。 如果将整数表示为素数之积, 则容易确定两个正整数的最 大公因子 下列关系总是成立的 如果k=gcd(a, b), 则 kp =min(ap , bp ), 对于任意的p∊P 例子： 300=22x31x52, 18=21x32 , gcd(18, 300)=21x31x50=6
82单向函数 One-way Function 单向陷井门函数One- way Trapdoor Function 定义8.1单向函数( One-way function) 函数f若满足下列条件,则称f为单向函数: (1)对于所有属于f之域的任一X,容易计算y(x) (2)对于几乎所有属于f之域的任一y求得x使≠=x),在计算上 不可行。 定义82单向陷井门函数(One- way Trapdoor Function) 可逆”函数f若满足下列两条件,则称F为单向陷井门函 数 (1)对于所有属于F之域的任一X,容易计算尺(x)=y (2)对于几乎所有属于f之域的任一%除非获得暗门信息 trapdoor),否则求出x,使得ⅹ=F1(y在计算上不可行,F1 为F之逆函数;如有额外信息暗门),则容易求出x=F1(,如 旅馆房间门。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 10/81
mfy@ustc.edu.cn 现代密码学理论与实践 10/81 定义8.1 单向函数(One-way Function) 一函数f 若满足下列条件, 则称f 为单向函数： (1)对于所有属于f 之域的任一x, 容易计算y= f(x) (2)对于几乎所有属于f 之域的任一y, 求得x, 使y= f(x), 在计算上 不可行。 定义8.2 单向陷井门函数(One-way Trapdoor Function) 一“可逆”函数F若满足下列两条件, 则称F为单向陷井门函 数： (1)对于所有属于F之域的任一x, 容易计算F(x)=y； (2)对于几乎所有属于F之域的任一y, 除非获得暗门信息 (trapdoor), 否则求出x, 使得 x = F -1 (y)在计算上不可行, F -1 为F之逆函数; 如有额外信息(暗门), 则容易求出x = F -1 (y)，如 旅馆房间门
单向函数举例 1离散对数问题 Discrete logarithm Problem(DP 令素数p满足p-1含有另一大素数q(q整除p-1)及一整数 g,1<g<p-1 若给定整数X,求y= gx mod p,最多需要Llog2X」 +W(X)-1次乘法,W(X)为X中所有1的个数。如X=15,即 X=(111)2,Wx)=4,则g15=(g2)g)2·g)2gmod p,只需要3+4-1=6次乘法。 但是若给定p,g及y,求x,则为DLP问题,最快方法需 要L(p)=exp{(np)l/3(n(np)2/3}次运算。 当p=512位时,L(p)约为2256≈1077,计算上不可行, 因为2100%1030,计算要1016年。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 11/81
mfy@ustc.edu.cn 现代密码学理论与实践 11/81 1.离散对数问题Discrete Logarithm Problem (DLP) 令素数p满足p-1含有另一大素数q (q整除p-1)及一整数 g, 1<g< p-1。 若给定整数x, 求y = gx mod p, 最多需要Llog2x｣ +w(x)-1次乘法, w(x)为x中所有1的个数。如x =15, 即 x =(1111)2 , w(x)=4, 则g15 =((g2)g)2·g)2·g mod p, 只需要3 + 4 -1=6次乘法。 但是若给定p, g及y, 求x, 则为DLP问题, 最快方法需 要L(p)=exp{(lnp) 1/3(ln(lnp)) 2/3 }次运算。 当p=512位时, L(p)约为2256≈1077 , 计算上不可行, 因为2100≈1030 , 计算要1016年
单向函数举例(续) 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/81
mfy@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)