发信人: caoyi1221(珠穆亚纳)
整理人: charmer(2004-07-01 10:25:50), 站内信件
|
数海拾贝之8
在数论中，有一个奇怪的现象，就是1、大合数的因子分解难上加难，至今进展不大。2、大素数的判定办法步步进展，已经取得突出的成就。
素数判定的方法，从原始的试除法到现代利用计算机判定素数的方法，判断一个大数是否是素数的方法方面，进展非常迅速。请看下面的比较：
方法 20位数 50位 100位 200位 1000位
试除法 2小时 10^11年 10^36年 10^86年 10^486年
威廉斯
方法 5秒 10小时 100年 10^9年 10^44年
艾德利曼和
鲁梅利法10秒 15秒 40秒 10分 1周
马宁德拉.阿格拉瓦法 很短时间（决定于计算机的性能）。
到印度理工学院的马宁德拉.阿格拉瓦法产生，震撼了数学界，到此为止,关于素数的判定,已经不是什么难以解决的问题了。大数也是如此。为什么？因为他们采用了非常高明的思路来解决大素数的判定。
其他判定大数为素数的方法，都是直接从是否为素数这个问题来思考。而马宁德拉.阿格拉瓦和他的两位在校本科生尼拉叶.卡亚尔、尼汀.萨克司特纳则另辟蹊径，将待判定大数的问题转化为一系列小问题和方程,写出了最简单有效的"素数判定算法",只用13行便已经写明。从此，关于素数判定，已经达到了非常实用的程度了。
但是，关于一个大合数分解为素因子的概率计算算法，至今仍然基本上是“试除法”的改进，所以，分解一个充分大的合数为素因子乘积的方法，进展不大。使用价值也不明显。在马宁德拉.阿格拉瓦素数判定法产生之后，曾经有一些利用素数加密法维护因特网安全的专家产生极大的担忧。他们认为，既然存在着简单的素数判定方法，也就可能存在简单的素因子分解算法，只不过我们还没有发现罢了。但是英国加密安全公司的本.哈德利认为：相对于原来的概率计算算法，新算法没有给素因子分解提供好的算法，所以这个突破没有威胁密码安全行业。
伊恩.斯图尔特的评价是：这一理论突破本身意义重大，但是其中带来的启发作用意义更加深远。两名本科生的毕业项目产生的重大成果提醒所有的数学工作者：我们可能忽略了很多重大数学问题的简单解决方法。
总之，大合数的素因子分解也可能存在着这种方法，只是还没有被发现，这是一个尚待解决的问题。
所以说，关于大合数分解、大素数应用问题，好象是一个一条腿长、一条腿短的残疾巨人。
谁是治疗这个残疾巨人的功臣？
（附：素数判定算法（当且仅当n为素数时，最终输出数才为素数））
lnput： integer n>1
1.if (n is of the form a^b, b>1)output COMPOSITE;
2.R=2
3.while (r<n) ｛
4. if(ged(n,r)≠1) output COMPOSITE;
5. if(r is prime)
6. let q be the largest prime factor of r-1
7. if(q≥4^r/2 logn)and (n(r-1)/q≠1(mod r))
8. break;
9. r←r+1;
10. ｝
11.for a=1 to 2r^1/2 logn
12. if ((x-a)^n≠(x^n-a)(mod x^r-1,n))output COMPOSITE;
13.output PRIME;
|
|