合数的素因子分解 分解一个数η就是把它写成其他数的乘积形式,如 n=a×b×C 比起用乘的方法把几个因子乘起来生成合数,分解 合数通常要困难得多。 (算术基本定理)任何整数a>1,都可以唯一地分 解为a=p1ap2pat,其中,p1<p2<.<p是素 数,所有的a都是非负整数。如91=7×13; 3600=24×32x52:11011=7×112×13 素因子分解就是把一个合数写成若干素数的乘积形 式,如3600=24×32×52, a=∏P“其中每个20,对于某整数a, 其大多数指数a为0 D∈D 2021/1/27 现代密码学理论与实践-08 7/692021/1/27 现代密码学理论与实践-08 7/69  分解一个数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