欧拉伪素数

欧拉伪素数（）是伪素数的一种。对于奇合数n以及与其互素的自然数a，如果
: a^{(n-1)/2} \equiv \pm 1\pmod{n}
成立，则称n为关于a的欧拉伪素数。欧拉伪素数是费马伪素数的推广，所有欧拉伪素数同时也是费马伪素数。

与费马伪素数类似，欧拉伪素数的定义也是源于费马小定理。该定理表明，对于素数p以及整数a，有 ap−1 = 1 (mod p)。对大于2的素数p，p可以表示为2q + 1 ，其中q为整数。于是a(2q+1) − 1 = 1 (mod p) 成立。再进一步化简为a2q − 1 = 0 (mod p)。通过因式分解，得到(aq − 1)(aq + 1) = 0 (mod p)，即a(p−1)/2 = ±1 (mod p)。

上式可以用作概率素性检验，其可靠性是费马素性检验的两倍。不过无法基于欧拉伪素数对素数进行确定性检验，因为存在绝对欧拉伪素数，即其关于所有与其互素的数都是欧拉伪素数。绝对欧拉伪素数是卡迈克尔数（即绝对费马伪素数）的子集。最小的绝对欧拉伪素数为1729 = 7×13×19。

示例
关于n的最小欧拉伪素数
参见

• 欧拉－雅可比伪素数
• 费马伪素数
• 強偽質數
• 卡迈克尔数

参考文献
*M. Koblitz, "A Course in Number Theory and Cryptography", Springer-Verlag, 1987.
*H. Riesel, "Prime numbers and computer methods of factorisation", Birkhäuser, Boston, Mass., 1985.