282842712474 发表于 2010-9-4 20:09:51

咨询几个关于素数的问题

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

好地方 发表于 2010-9-5 15:19:20

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

gxqcn 发表于 2010-9-5 21:28:07

梅森数 2^p-1 有专门的素性检测算法，叫Lucas-Lehmer Test ，
这是一个高效且确定性的算法。
页: [1]
查看完整版本: 咨询几个关于素数的问题