咨询几个关于素数的问题

282842712474

1、尽管伪素数很多，但是貌似还没有发现形如$2^p-1$的伪素数，那么用费马小定理来判定梅森数的素性效率如何？（计算$2^(2^p-2) Mod (2^p-1)$） 2、就目前所使用的素数判定算法（包括概率性的，这种算法是指通用的算法，而不是判定某一类数的算法），可以在有限时间内判断出多少位数字的素性？ 当然这个有效时间说法太过简单了，可以使用“判断n位数需要m时间”来回答。 3、对于上千位数甚至上万位数p，计算$2^p Mod p$是否还有意义？ 第三问其实与第一问等价。

好地方

如果p是素数，则2^p-1不是真素数就是以2为底的伪素数。比如2^2046≡1 mod 2047

gxqcn

梅森数 2^p-1 有专门的素性检测算法，叫Lucas-Lehmer Test ， 这是一个高效且确定性的算法。