合数的素因子分解 任一给定的正整数,可通过简单列出所有后面公式中 非零指数分量来说明 ■ 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 现代密码学理论与实践 /81mfy@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