部分形如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%