江苏龙网

  1. 首页 > 生活 > >

为何直接用费马小定理进行质数测试会出错?

如果是说miller rabin，不是每个数都会被选一次用来做测试的，没有选出能说明被测试数非质数的也有可能。(如果每个数都测一遍，也就不是蒙特卡罗方法了，在效率上也没有优势)
■网友
有一定概率是错误的，但是效率很高。
■网友
卡米歇尔数的定义是若一个合数n，对于所有与其互质的数a，都满足a^(n - 1) == 1 (mod n)，则称它为卡米歇尔数。
但是当a不与n互质时，则此情形不成立（大概是这样，我没自己证。）理所应当的，费马检测是可以检测卡米歇尔数的。
【为何直接用费马小定理进行质数测试会出错?】 但是啊，在卡米歇尔数特别大时费马检测就不那么有效（有效指的是效率高，本身费马检测还是对的）了（请想一想为什么）。
但其实在应用上这不构成什么问题，因为卡米歇尔数并不多。

■网友
Fermat小定理只是素数的必要条件，但并不是充分条件
■网友
这561=3*11*17，你连应用定理的前提条件都不符合。前提条件是a,p的最大公约数为1，p为质数。然后你的这个例子，非常友好地将两个条件都违背了，561不是质数，3和561不是互质的，结果不对你还怪定理？
■网友
因为p不一定是素数，所以a和p不一定互素，然后你就不能用费马小定理了
■网友
Carmichael数需要排除a和n不互素的情况 费马小定理的前提是p是素数 而不是同余成立
■网友
概率算法，优点是快
■网友
你的问题很简单，这个a存在，不意味着你能在有限次尝试中找到它。


    推荐阅读


    上一篇：自己学习c/c++，有啥推荐的书吗

    下一篇：内置商城的游戏，不删档公测和正式运营有啥区别