欧拉伪素数 欧拉伪素数英語Euler pseudoprime是伪素数的一种对于奇合数n以及与其互素的自然数a如果 a  n          mod n  displaystyle anequiv pm pmod n 成立则称n为关于a的欧拉伪素数欧拉伪素数是费马伪素数的推广所有欧拉伪素数同时也是费马伪素数 与费马伪素数类似欧拉伪素数的定义也是源于费马小定理该定理表明对于素数p以及整数a有 ap   mod p对大于的素数pp可以表示为q   其中q为整数于是aq     mod p 成立再进一步化简为aq     mod p通过因式分解得到aq  aq     mod p即ap   mod p 上式可以用作概率素性检验其可靠性是费马素性检验的两倍不过无法基于欧拉伪素数对素数进行确定性检验因为存在绝对欧拉伪素数即其关于所有与其互素的数都是欧拉伪素数绝对欧拉伪素数是卡迈克尔数即绝对费马伪素数的子集最小的绝对欧拉伪素数为