1.2.3　分解素因数

每个合数都可以写成几个素数相乘的形式，并且这种表示形式是唯一的.这个结论称为算术基本定理.其中每个素数都是这个合数的因数，称为这个合数的素因数.例如，15=3×5，3和5称为15的素因数.把一个合数用素因数相乘的形式表示出来，称为分解素因数.例如，把28分解素因数：28=2×2×7.

显然，每个偶数都有素因数2.分解素因数的问题变为奇数的素因数分解问题.

分解素因数的方法有多个，目前的研究也很活跃.

1.试除法

试除法就是尝试的整数是否整除n.如果能整除则得到一个素因数和商.从该素因数开始继续对该商进行尝试，直到尝试的素因数等于尝试的商为止，或者尝试的素因数大于为止.

2.试拆法

试拆法就是尝试将奇数n表示成m个连续整数的和.例如，51=16+17+18=3×17.试拆法的过程就是从1开始寻找若干连续整数的和的过程，全程不用除法.用试拆法分解51的素因数的过程如下：

51<1+2+3+4+5+6+7+8+9+10=55

51<2+3+4+5+6+7+8+9+10=54

51<3+4+5+6+7+8+9+10=52

51>4+5+6+7+8+9+10=49

51<4+5+6+7+8+9+10+11=60

51<5+6+7+8+9+10+11=56

51=6+7+8+9+10+11=（6+11）/2×6=17×3

3.费马整数分解方法

费马整数分解方法基于以下事实：如果正整数N=2n+1，那么存在正整数a，b使得a2-b2=N.假设N=cd，那么c和d必为奇数，令，不难验证a2-b2=N.因为（n+1）2-n2=N，方程x2-y2=N至少有一组整数解，如果（x，y）=（a，b）是它的一组正整数解，那么，可见a取值于之间.费马整数分解的算法描述如下：

输入：正奇数N.

输出：无.

返回：N的一个因子.

（1）令；

（2）令，b=a2-N；

（3）如果b是一个完全平方数，转（5）；

（4）令a=a+1，b=a2-N，转（3）；

（5）返回，结束.

如果费马整数分解算法返回的值为1，则说明N为素数.费马整数分解方法只是分解出整数的一个因子，不像试除法那样分解出整数的各个素数因子.如果希望用费马整数分解方法分解出整数的各个素因子，可以反复使用该方法.

例1.2.1　分解253.

所以，一个因子是11，另一个是253/11=23.

4.其他方法

从上述介绍中，可以感觉到整数素因子分解的工作主要是搜索，对于大整数而言，其计算量是巨大的.著名的公开密钥RSA系统就是建立在大整数的分解极其困难的理论基础上的.正是由于计算机的迅猛发展，随着加密与破密的对抗和数论自身理论的提高，整数分解的研究变得特别活跃，算法不断得到改进，整数分解素因数的算法还有二次筛法、数域筛法、连分数算法、椭圆曲线法等.目前，对于大整数的分解计算量都是非常大的.目前公认最快的整数素因子分解算法称为量子算法，其建立在未来的量子计算机上.