部分形如2^p-1的梅森数的快速查找素因子的方法

qianyb

当p 是素数，且p 模60等于11或23或59,且2p+1也是素数时，2^p-1的一个因子是2p+1(像此类的数在p<50亿内的有约700万个） 当p是合数时，2^p-1的一个因子是2^k-1(k是p的一个因子），如2^9-1的一个因子是2^3-1

KeyTo9_Fans

你的结论貌似有点弱。 可能在座的大牛们都知道这些结论。 而且说不定他们知道的比你提到的这些结论更深刻。 比如：$p$模$60$等于$11$、$23$、$59$这个条件也许可以加强。 正如 wiley 大牛提到的：

mathworld上有给(倒数第二段): "If $n-=3\ (mod\ 4)$ is a prime, then $2n+1$ divides $2^n-1$ iff $2n+1$ is prime." 所以楼主给出的这个数有可能是利用这个结果构造的. wiley 发表于 2010-1-29 03:06

qianyb

哦，不知谁可以分享一下大数分解的知识或代码

wiley

2# KeyTo9_Fans 楼主的说法和mathworld上的应该是等价的. 因为如果p是4m+3的质数, 而且2p+1也是质数, 那mod 60就只可能是11, 23, 59, 不然要不p被3或5整除, 要不2p+1被3或5整除. 所以楼主的结果在查找这些数的时候效率高很多. 不过我不了解找到这些合数有什么用, 楼主有机会可以科普一下.

qianyb

可以排除这种梅森数形式的数不是素数，在p（p为素数）<50亿的梅森形式数中约占2%