● 判定素数的初步方法 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: Begin (白云), 信区: Program
标题: 判定素数的初步方法
发信站: BBS 荔园晨风站 (Fri Apr 30 10:34:48 1999), 转信

发信人: newton (三强), 信区: Math
标题: 判定素数的初步方法
发信站: BBS 一网情深站 (Wed Apr 28 23:28:50 1999), 转信

——费马小定理。

大家都知道费马大定理：x^n + y^n = z^n无整数解 (n >= 3)
这已经证明了。Andrew Wiles 1995 princeton

费马小定理也很有名: a^p = a (mod p) 其中p为素数，a为任意整数。
推论：a^(p-1) = 1 (mod p)

这个定理给出了一种初步判定素数的极有效的方法：
假设待判定的数为n，任取一个整数（一般取已知素数）a > 1，
计算a^(n-1) mod n，计算方法很简单很有效，大概是辗转相除法吧，
我也不知道:)如果余数不是1，那么n为合数（不是素数）。如果是1，
那么n有可能是素数（不一定），把这样的n叫做一个a-PRP，如果一个
a-PRP不是素数，我们把它叫做伪素数。伪素数是很少的，非常非常少。
比如在25,000,000,000之内大约有1,000,000,000个2-PRP或素数，其中
只有21853个伪素数。很遗憾，任意a-PRP中都有无穷多的伪素数。
可以用多条件来排除，2-PRP，3-PRP，5-PRP……，不过有的数用所有
的a来测试，余数都为1，除非用它的约数。这是这种方法的致命弱点，
这样的数叫做Carmichael数。一个坏消息：Carmichael数也有无穷多个。

--
流水下滩非有意，白云出轴本无心。
如此星辰如此夜，为谁不寐立中宵。

※ 来源:．BBS 荔园晨风站 bbs.szu.edu.cn．[FROM: 192.168.1.56]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店