[转]因数的分解

因数的分解 来源：数学学习  作者：  日期：2005-4-9 22:38:14

数的素性检验方法问题在近几年得到了飞速的发展,过去,要检验一个数 n 是否是素数,最简单的方法是用试除法,用小于n的平方根以下的所有素数去除n,若都除不尽,则n就是素数,否则为合数.这对于比较小的数来说还适用,若用计算机编成程序,对于10位数,几乎瞬间即可完成,对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人吃惊的是,要检验一个一百位数,需要的时间就猛增到10^36年.到了1980年,这种困难的情况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法,检验一个20位数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟,如果要他检验一个1000位数,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个数是否是素数.

那么,如何去找合数的因子呢?试除法显然不适用于大数的因数分解,但实际上,目前所有用于素性检验和因数分解的方法中又都少不了试除法.一般在开始时它的运算并不慢,比如先用前一百万个素数去试除,如果找到一个因数,那么素性和因数分解问题就都解决了.若未找到,这时他如果是合数,就只有极大的因数,费马曾经找到了一种极其简单的对付这种情况的方法,以下就是这种方法的简单说明:

设n=uv,u和v都是大的奇数,不妨设u<=v令x=(u+v)/2,y=(v-u)/2.于是,0<=y<x<=n,且v=x+y,u=x-y故n=uv=(x+y)(x-y)=x*x-y*y或者      y*y=x*x-n,若能找到两个数x,y满足前式,则 n=(x+y)(x-y),即得出了n 的因数分解.费马本人就是用此方法找到了2027651281=44021X46061.可以这样进行,找出k>=√n 然后从x=k 开始,依次检验x=k+1,x=k+2...这些数是否能使x*x-n成为平方数,一旦找到这样的x,当然分解工作就完成了.倘若n有两个大小相近的因数,则其中之一能很快找到.你可以用此方法试着分解一下10379.另外,在判断x*x-n是否是平方数时,可以排除个位数是2,3,7,8的情况,因为没有一个平方数是以2,3,7,8结尾的.

URL http://hahz.com/gb/sxdt/054922432593280.shtml