0 0最喜欢这种数学书了，没有高深到让人摸不着头脑的偏难理论，语言也并不死气沉沉的，噗哈哈哈哈，虽然是本1999年的老书
沙里淘金寻因子
把一个大数分解因子是数论中最富挑战性的问题之一。读者应当记得，某数的一个因子就是能够整除该数的任何一个数；如果一个数除了1和它自身之外没有其他任何因子，则这个数就是素数。其次再来谈一点“布局”的情况。“素数王国”——由素数组成的世界——在数轴上的分布趋势是越来越稀疏，而且是相当随机的（0 0这句话便是说明了素数列是写不出通项公式的，XD）。但因子王国——这是一个整数世界，则大不相同。素数东一个西一个地嵌插在因子王国中。大多数的数都不是素数。很明显，有一半的数是2的倍数，1/3的数是3的倍数，而2/3的数不是2的倍数就是3的倍数。但是有相当大一部分数没有小因子。如果你能找到某数的哪怕一个因子，那么剩下的因子就是此因子除该数后所得的商的因子，而上比原来的那个数要小。因此，难就难在要找到第一个因子。
这的确是件名副其实的难事：1903年，美国数学家F.N.Cole花了3年的星期天用纸和笔进行计算后发现了2^67-1=193707721×761838257287（0 0钦佩一下）。佐治亚大学的Carl Pomerance在1996年12月号《美国数学学会通告》上考察了这方面的最新进展。
学校里教的把一个数分解因子的方法是形式化的试错法：先用2来试除，然后是3，这样试除下去直到该数的平方根。此方法的效率低的无可救药。到1970年，改进了的因子分解法只能对付有20位的任意数字。到1980年，位数上限已上升到50位。到1990年达116位，1994年达129位。1996年，一个新的最佳算法诞生了，它成功的分解了一个130位的数字，所需时间只有先前方法的1/6。
这一改进部分应归功于计算机功能的增强。然而，把计算机运行速度提高100万倍只能使因子分解的记录又增加几位数。因此，主要的改进在于概念上的进步。
把一个大数分解因子是数论中最富挑战性的问题之一。读者应当记得，某数的一个因子就是能够整除该数的任何一个数；如果一个数除了1和它自身之外没有其他任何因子，则这个数就是素数。其次再来谈一点“布局”的情况。“素数王国”——由素数组成的世界——在数轴上的分布趋势是越来越稀疏，而且是相当随机的（0 0这句话便是说明了素数列是写不出通项公式的，XD）。但因子王国——这是一个整数世界，则大不相同。素数东一个西一个地嵌插在因子王国中。大多数的数都不是素数。很明显，有一半的数是2的倍数，1/3的数是3的倍数，而2/3的数不是2的倍数就是3的倍数。但是有相当大一部分数没有小因子。如果你能找到某数的哪怕一个因子，那么剩下的因子就是此因子除该数后所得的商的因子，而上比原来的那个数要小。因此，难就难在要找到第一个因子。
这的确是件名副其实的难事：1903年，美国数学家F.N.Cole花了3年的星期天用纸和笔进行计算后发现了2^67-1=193707721×761838257287（0 0钦佩一下）。佐治亚大学的Carl Pomerance在1996年12月号《美国数学学会通告》上考察了这方面的最新进展。
学校里教的把一个数分解因子的方法是形式化的试错法：先用2来试除，然后是3，这样试除下去直到该数的平方根。此方法的效率低的无可救药。到1970年，改进了的因子分解法只能对付有20位的任意数字。到1980年，位数上限已上升到50位。到1990年达116位，1994年达129位。1996年，一个新的最佳算法诞生了，它成功的分解了一个130位的数字，所需时间只有先前方法的1/6。
这一改进部分应归功于计算机功能的增强。然而，把计算机运行速度提高100万倍只能使因子分解的记录又增加几位数。因此，主要的改进在于概念上的进步。
