合数的素因子分解 。分解一个数就是把它写成其他数的乘积形式，如 n=axbXc ● 比起用乘的方法把几个因子乘起来生成合数，分解 合数通常要困难得多。 任何整数a>1,都可以唯一地分解为a=p1ap22.…pat, 其中，p1<p2<<p是素数，所有的a都是正整数。 如91=7x13;3600=24x32x52:11011=7x112x13 素因子分解就是把一个合数写成若干素数的乘积形 式，如3600=24x32X52, a= 其中每个a,≥0，对于某一整数a, 其大多数指数a为0. p∈P 2022/10/9 现代密码学理论与实践-08 7170
2022/10/9 现代密码学理论与实践-08 7/70 合数的素因子分解 ⚫ 分解一个数n就是把它写成其他数的乘积形式，如 n=a×b×c ⚫ 比起用乘的方法把几个因子乘起来生成合数，分解 合数通常要困难得多。 ⚫ 任何整数a>1, 都可以唯一地分解为a= p1 a1p2 a2…pt at , 其中, p1<p2<…<pt 是素数，所有的ai都是正整数。 如91=7x13; 3600=24x32x52 ; 11011=7x112x13 ⚫ 素因子分解就是把一个合数写成若干素数的乘积形 式，如3600=24x32x52 ， 其中每个ap≥0, 对于某一整数a， 其大多数指数ap为0. = p P ap a P
合数的素因子分解 车不 105 ● 任一给定的正整数，可通过简单列出所有后面公式中 非零指数分量来说明. Ex:12可以表示为{a2=2,a3=1};18可以表示为 {a2=1,a3=2};91可以表示为{a7=1,a13=1} ● 两个数的乘法等同于对应指数分量的加法 k=mn→k。=m。+np对所有p Ex:k=12x18=(22X3)x2x32)=216,k2=2+1=3, k3=1+2=3,.∴.216=23x33 任何以p形式表示的整数仅能被对应素数分量小于 或等于它的另一个整数p整除，其中k,即有b →apb。,对所有素数p成立。 Ex:a=12,b=36,1236,12=22x31,36=22x32 a2=2=b2,a3=1≤2=b3 2022/10/9 现代密码学理论与实践-08 8/70
2022/10/9 现代密码学理论与实践-08 8/70 合数的素因子分解 ⚫ 任一给定的正整数, 可通过简单列出所有后面公式中 非零指数分量来说明. 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 ⚫ 任何以p k形式表示的整数仅能被对应素数分量小于 或等于它的另一个整数p j 整除, 其中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 15 gcd(a,b)=c,即c是a和b的最大公约数，当 1.c是a和b的因子 2.任何a和b的因子也是c的因子 ● 下列关系总是成立的 如果k=gcd(a,b),则kp=min(ap,bp),对于任意的p∈P 两个整数a,b,如果除了1以外没有公共因子，则称它们互 素(Relatively Prime) 8和15互素，因为8的因子是1,2,4,8，而15的因子是1,3,5,15， 1是它们唯一的公共因子。 如果将整数表示为素数之积，则容易确定两个正整数的最 大公因子 300=22x31x52,18=21x32,gcd(18,300)=21x31x50=6 2022/10/9 现代密码学理论与实践-08 9/70
2022/10/9 现代密码学理论与实践-08 9/70 互素和最大公约数GCD ⚫ gcd(a, b)=c, 即c是a和b的最大公约数, 当 1. c是a和b的因子 2. 任何a和b的因子也是c的因子 ⚫ 下列关系总是成立的 如果k=gcd(a, b), 则 kp =min(ap , bp ), 对于任意的p∊P ⚫ 两个整数 a, b, 如果除了1以外没有公共因子, 则称它们互 素(Relatively Prime) 8和15互素, 因为8的因子是1,2,4,8, 而15的因子是1,3,5,15, 1是它们唯一的公共因子。 ⚫ 如果将整数表示为素数之积, 则容易确定两个正整数的最 大公因子 300=22x31x52 , 18=21x32 , gcd(18, 300)=21x31x50=6
单向函数One-way Function 单向陷井门函数One-way Trapdoor Function 定义8.1单向函数(One-way Function) 一函数f若满足下列条件，则称f为单向函数： (1)对于所有属于f之域的任一x,容易计算y=x) (2)对于几乎所有属于f之域的任一y,求得x,使y(x),在计算上不 可行 定义8.2单向陷井门函数(One-way Trapdoor Function) 一“可逆”函数F若满足下列两条件，则称F为单向陷井门函 数： (1)对于所有属于F之域的任一X,容易计算F(X)=y; (2)对于几乎所有属于F之域的任一y,除非获得暗门信息(trapdoor) 否则求出X,使得X=F1(y)在计算上不可行，F1为F之逆函数： 如有额外信息（暗门），则容易求出×f1炒，如旅第太平的。 2022/10/9 现代密码学理论与实践-08 10/70
2022/10/9 现代密码学理论与实践-08 10/70 单向函数One-way Function 单向陷井门函数One-way Trapdoor Function 定义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)，如旅馆太平门
单向函数举例 15 1.离散对数问题Discrete Logarithm Problem(DLP) 令素数p满足p-1含有另一大素数q(q整除p-1)及一整数g, 1<g<p-1。 若给定整数x,求y=g×modp,最多需要Llog2X+w(X)-1次 乘法，w(X)为x中所有1的个数。如x=15,即 ×=(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(Inpln(lnp)}次运算。 当p=512位时，L(p)约为2256≈1077，计算上不可行，因为 2100≈1030，计算要1016年。 2022/10/9 现代密码学理论与实践-08 11/70
2022/10/9 现代密码学理论与实践-08 11/70 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, 则g 15 =((g2 )g)2·g)2·g mod p, 只需要 3 + 4 -1=6次乘法。 但是若给定p, g及y, 求x, 则为DLP问题, 最快方法需要 L(p)=exp{(lnpln(lnp))½ }次运算。 当p=512位时, L(p)约为2 256≈1077 , 计算上不可行, 因为 2 100≈1030 , 计算要1016年。 单向函数举例