Perrin 伪素数与费马小定理伪素数

282842712474

Perrin 伪素数 定义 f(n) = f(n - 2) + f(n - 3) ，其中 f(1) = 0 ， f(2) = 2 ， f(3) = 3 。这个数列叫做 Perrin 数列。 似乎有这么一个规律： n 能整除 Perrin 数列的第 n 项 f(n) ，当且仅当 n 是一个素数。如果这个规律成立的话，我们也将获得一个效率非常高的素数检验方法。根据 MathWorld 的描述，1899 年 Perrin 本人曾经做过试验，随后 Malo 在 1900 年， Escot 在 1901 年，以及 Jarden 在 1966 年都做过搜索，均未发现任何反例。直到 1982 年， Adams 和 Shanks 才发现第一个反例 n = 271 441 ，它等于 521 × 521 ，却也能整除 f(271 441) 。下一个反例则发生在 n = 904 631 的时候，再下一个反例则是 n = 16 532 714 。这种反例被称为 Perrin 伪素数。 首先，Perrin的规律是否是一个素数的必要条件？（就好像满足费马小定理是一个数为素数的必要条件一样？） 那么这种Perrin 伪素数和费马小定理所产生的伪素数有没有重叠呢？ 要是没有的话，两种算法加起来，不是可以得到一个高效率的确定性素性判断方法？

mathematica

我曾经和你一样沉迷于这类破问题！！！！！！！！！！ 但是我现在必须说在概率中生存！ baillie-psw就是很好的算法了

mathematica

你为什么不到维基百科上去找呢？

mathematica

“两种算法加起来，不是可以得到一个高效率的确定性素性判断方法？” 在你想这个问题的时候，别人已经想过了！ 计算量也增大了，你发现了吗？不要再研究这个破问题了！

mathematica

但是我知道：物不极难反！ 我想你是不撞南墙不回头的！ 当你被挫折了，我想你应该会知道回头了！！！！！！！！！！

mathematica

https://en.wikipedia.org/wiki/Perrin_number#Perrin_pseudoprimes
http://mathworld.wolfram.com/PerrinPseudoprime.html
https://oeis.org/A013998

多看看维基百科,有助于你了解前人的工作

这儿带因数分解的
https://oeis.org/A013998/a013998.txt

mathematica

mathematica 发表于 2019-1-25 13:34
https://en.wikipedia.org/wiki/Perrin_number#Perrin_pseudoprimes
http://mathworld.wolfram.com/Perrin ...

perrin绝大多数是两个因子,而卡米歇尔数至少三个因子,
所以用来刨除这个数比较好

nyy

Baillie_PSW素性判定的mathematica代码（有详细解释）
https://bbs.emath.ac.cn/forum.ph ... 6&fromuid=14149
(出处: 数学研发论坛)

https://oeis.org/A013998/a013998.txt 这边的所有伪素数，用lucas素性判定，全部false，总共{{False, 3810}}个