主题
Search

卢卡斯伪素数

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

当 P 和 Q 是 整数 且 D=P^2-4Q!=0 时，通过以下方式定义 卢卡斯序列 {U_k}

U_k=(a^k-b^k)/(a-b)

对于 k>=0，其中 a 和 b 是 x^2-Px+Q=0 的两个 根。然后，将卢卡斯伪素数定义为 奇 合数 n，使得 nQ，雅可比符号 (D/n)=-1，且 n|U_(n+1)。

同余式 L_n=1 (mod n) 对每个素数 n 都成立，其中 L_n 是 卢卡斯数。然而，一些合数也满足此同余式。对应于卢卡斯数 L_n 特例的卢卡斯伪素数是那些满足 n|(L_n-1) 的合数 n。 其中前几个是 705, 2465, 2737, 3745, 4181, 5777, 6721, ... (OEIS A005845)。

Wolfram 语言 实现了基于底 2 和 3 的多重 Rabin-Miller 测试，并结合卢卡斯伪素数测试作为函数中的 素性测试PrimeQ[n]。

另请参阅

超强卢卡斯伪素数, 卢卡斯数, 卢卡斯序列, 伪素数, 强卢卡斯伪素数

使用 探索

参考文献

Baillie, R. and Wagstaff, S. S. Jr. "Lucas Pseudoprimes." Math. Comput. 35, 1391-1417, 1980.Bruckman, P. S. "Lucas Pseudoprimes are Odd." Fib. Quart. 32, 155-157, 1994.Ribenboim, P. "Lucas Pseudoprimes (lpsp(P,Q))." §2.X.B in The New Book of Prime Number Records, 3rd ed. New York: Springer-Verlag, p. 129, 1996.Sloane, N. J. A. Sequence A005845/M5469 in "The On-Line Encyclopedia of Integer Sequences."

在 中被引用

卢卡斯伪素数

请引用为

Weisstein, Eric W. “卢卡斯伪素数。” 来自 Web 资源。 https://mathworld.net.cn/LucasPseudoprime.html

主题分类