答案是无穷多个。实际上,数学家迈 罗在1903年证明,如果n为伪素数, 那么2^n-1也是伪素数。 不过,同素数个数相比,伪素数的个 数非常少。例如,在2x10~10之内 伪素数不到素数的百万分之三。因此, 可以认为 Fermat定理的逆定理几乎成 立
答案是无穷多个。实际上，数学家迈 罗在1903年证明，如果n为伪素数， 那么2^n-1也是伪素数。 不过，同素数个数相比，伪素数的个 数非常少。例如，在2x10^10之内， 伪素数不到素数的百万分之三。因此， 可以认为 Fermat定理的逆定理几乎成 立
利用伪素数表,可以给出判别素数的新方 法:如果p不整除2^n-1,则p为合数;如果 p整除2^n-1,且在伪素数表中,则为合数 否则,p是素数。 伪素数可以推广到a-伪素数。令人惊奇的 是,存在这样的数p,它对任何a都是伪素 数。例如,561=3x11x17就是这样一个伪 素数,即a10=1(md561)
• 利用伪素数表，可以给出判别素数的新方 法：如果p不整除2^n-1, 则p为合数；如果 p整除2^n-1, 且在伪素数表中，则p为合数， 否则，p是素数。 • 伪素数可以推广到a-伪素数。令人惊奇的 是，存在这样的数p, 它对任何a都是伪素 数。例如，561=3x11x17就是这样一个伪 素数，即 1 (mod 561) 560 a
这样的数称为绝对伪素数,也称迈克尔 数。如果迈克尔数只有有限个,则对 n>M,素数的判别变得比较容易。但迈克 尔可能有无限个,这使得直接用 Fermat 定理判别素性变得困难
• 这样的数称为绝对伪素数，也称迈克尔 数。如果迈克尔数只有有限个，则对 n>M, 素数的判别变得比较容易。但迈克 尔可能有无限个，这使得直接用Fermat 定理判别素性变得困难
n-1检验法 假设n-1=FR,F>R,gcd(FR)=1.如果对F的 每一个素因子q都存在一个整数a>1满足 a=l(mod n), gcd(a9-l, n)= 则n是素数
• n-1检验法 假设n-1=FR, F>R, gcd(F,R)=1. 如果对F的 每一个素因子q都存在一个整数a>1满足 则n是素数。 1 (mod ), gcd( 1, ) 1 1 ( 1)/ − = − − a n a n n n q
基于广义黎曼猜想的判别 1976年,缪内发现了素性判别与黎曼猜 想之间的一个深刻联系。他的结论是 在广义黎曼假设下,存在常数C,对任何 整数n,若n为合数,则存在aC(ogn)2 使得 C 12≠ (mod n)
• 基于广义黎曼猜想的判别 1976年，缪内发现了素性判别与黎曼猜 想之间的一个深刻联系。他的结论是： 在广义黎曼假设下，存在常数C, 对任何 整数n, 若n为合数，则存在a<C(logn)^2 使得 (mod ) 2 1 n n a a n −