[科普中国]-欧拉－雅可比伪素数

在数论中，奇数整数n被称为欧拉－雅可比伪素数（Euler–Jacobi可比伪素数）（或者更常见的是欧拉可能素数）。

介绍如果a和n是互质的，那么

mod

其中是雅可比符号。
如果是满足上述同余的奇数复合整数，那么被称为Euler-Jacobi pseudoprime（或者更常见的是Euler pseudoprime）以基于。

属性这个定义的动机是所有素数n满足上述等式的事实，如Legendre符号文章中所述。 可以相当快速地测试该等式，其可以用于概率素性测试。 这些测试的强度是基于费马小定理的测试的两倍1。

每个欧拉－雅可比伪素数也是Fermat pseudoprime和Euler pseudoprime。 正如卡迈克尔数字那样，没有任何数字是Euler-Jacobi伪像到所有基数。 Solovay和Strassen表明，对于每个复合物n，对于小于n的至少n / 2个碱基，n不是欧拉－雅可比伪素数.

最小的欧拉－雅可比伪素数2是561.有11347个欧拉－雅可比伪素数2小于25·109。

如上定义的欧拉－雅可比伪素数通常简称为Euler pseudoprime。

例子下表给出了基数n≤30的所有Euler-Jacobi假性小于100000。

|| ||

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所