费马素性检验

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

费马素性检验

点击查看词条快照

费马素性检验是一种质数判定法则，利用随机化算法判断一个数是合数还是"可能是"素数。概念. 根据费马小定理：如果"p"是素数，formula_1，那么 formula_2。如果我们想知道"n"是否是素数，我们在中间选取"a"，看看上面等式是否成立。如果对于数值"a"等式不成立，那么"n"是合数。如果有很多的"a"能够使等式成立，那么我们可以说"n"可能是素数，或者伪素数。在我们检验过程中，有可能我们选取的"a"都能让等式成立，然而n却是合数。这时等式 formula_3 被称为"Fermat liar"。如果我们选取满足下面等式的"a" formula_4 那么"a"也就是对于"n"的合数判定的"Fermat witness"。算法以及运行时间. 整个算法可以写成是下面两大部：输入："n"需要检验的数；"k"：参数之一来决定检验需要进行的次数。输出：当"n"是合数时输出合数，否则输出可能是素数：重复"k"次：在[2, "n" − 2]范围内随机选取"a" 如果"a""n" − 1 mod "n" ≠ 1那么返回合数返回可能是素数若使用模指数运算的快速算法，这个算法的运行时间是O("k"log2"n" log log n) = Õ("k" log2"n")，这里"k"是一个随机的"a"需要检验的次数，"n"是我们想要检验的数。缺点. 众所周知，对于卡米歇尔数"n"，全部令gcd("a","n")=1的"a"都是费马骗子数（Fermat liars）。尽管卡米歇尔数很是稀有，但是却足够令费马素性检验无法像如米勒-拉宾和Solovay-Strassen的素性检验般，成为被经常实际应用的素性检验。一般的，如果"n"不是卡米歇尔数，那么至少一半的 formula_5 是费马证人数（Fermat witnesses）。在这里，令"a"为费马证人数、"a"1, "a"2, ..., "a""s"为费马骗子数。那么 formula_6 所有的"a"×"a"i for "i" = 1, 2, ..., "s"都是费马证人数。应用. 加密程序PGP在算法当中用到了这个素性检验方法。

严用和

严仁

严羽

日本航空123号班机空难

严遂

香港小姐竞选

羊城通

对流层臭氧

自由女神像

哲学博士

医学士

教育博士