发信人: wasguru()
整理人: jeter(2000-02-11 16:59:23), 站内信件
|
【 在 styc (Frank!) 的大作中提到: 】
: 素数最常用的检验方法是试除。检验一个自然数n是否素数，只要拿小于或等于
: [sqrt(n)]的所有素数去除n，如果都不能整除，则n为素数，否则为合数。此方法
:
: 虽算法简单，但计算量大。当n非常大时（如n=2^6972593-1，2098960位数），即
: .......
当然有比这好得多的算法，否则象RSA之类的加密算法还怎么干活？这个算法称为
Miller-Rabin算法，但这个算法并不是100%准确的，也就是就，它有可能误判，
但是误判的概率可以做到很小。算法中有一个参数s，误判的概率小于1/2^s。显
然，取s=50的话，几乎就不会错了。这个算法的复杂度正比于s，正比于位数的3
次方，而试除法的复杂度是位数的指数函数。
算法的具体形式可以去找比较深一些的算法教材，这里说不清楚。
--
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 144.92.44.76]
|
|