四探素数与素数域——同周期分解的算理 倪则均，2015年6月18日。

n123zj3

（西汉杨雄的《太玄经》上说：“夫物不因不生，不革不成。
故知因而不知革，物失其则；知革而不知因，物失其均。”）
1，梅森数和费马数的来历。
首先发现梅森数的人是费马，并非是梅森（Mersenne，1588—1648）。费马在1640年6月，给梅森（Mersenne，1588—1648）的一封信中说：“如果n不是素数，则2n-1也不是素数，因此，2n-1型的素数只可能具有2p-1的形式，其中p是素数。可是反过来，2p-1型的数一般不是素数，而是复合数。”费马还说它的素因子只具有的形式。
另外，费马还知道，除非m是2的方幂，否则2m+1不可能是素数。从1640年起，他多次声称，反过来，2^2n+1是素数(后来被称为费马数)。当n=0，1，2，3，4时，2^2n+1的确是素数；可是当n=5时，欧拉硬凑出了它的一个因子为641，以后大家又陆续发现，随后的这类序列数都不是素数。费马一生对于素数作了大量的猜想，似乎只有对于费马素数的猜想是错的。
现在大家将2 p-1形素数称之为梅森素数，也决不是因为梅森对于这种类型的素数，作出了怎么重要的贡献。应该说是费马的上述那封信，才激发起了梅森研究2p-1型数的兴趣。梅森在1644年公开了他的研究成果，他指出当P=13，17，19，31，67，127，257时，这七个2p-1型数都是素数。显然，这是一个充满问题的成果，因为其中的67和257并不符合条件。其实在13≤p≤257之内，应该共有八个符合条件p存在，梅森又漏掉了61，89，107三个符合条件p。
由此可见，梅森的上述所谓成果，实际上只是他的一个猜想，根本没有经过实际验证。那么，后来之人又凭什么要将这种2p-1型数，命名为梅森形数呢？其实，其中另有更加重要的原因，那就是梅森的一生，对于后来西方数学的腾飞，作出了不可磨灭的贡献。应该说，梅森对于西方数学的腾飞所作出的贡献，远比笛卡尔（Descartes，1596—1650）、帕斯卡、乃至费马等人都要大得多。因此将2p-1形数命名为梅森形数，作为对于梅森的永久纪念。
梅森出生于法国一个普通劳动人民的家庭，家境比较贫困。梅森直到十六岁，才有机会进入拉夫莱什的耶稣会学校接受教育。此时贵族出身的笛卡尔，才八岁也进入了这个学校学习，因此梅森和笛卡尔之间，还有着五年的同学情谊。或许由于梅森刻苦勤奋的原因，随后他又得到了去巴黎神学院深造的机会。二年后他又加入了米尼姆教派，于是在1619年，梅森被派任为巴黎米尼姆修道院的主持。对于数学来说，尽管梅森的悟性不是很高，但是他十分喜爱数学，尤其热中于收集自古以来的各国的数学著作。
1626年梅森编辑出版了《数学汇编》，此书实际上是对外公布了，巴黎米尼姆修道院里的藏书内容。梅森的丰富的数学藏书，首先是将费马、笛卡尔、帕斯卡等法国数学家，吸引到了他的身边，同时也引起了其它各国数学家，乃至科学家们的高度关注。应该说，那时的米尼姆修道院，实际上已经成了，当时欧洲各国的学术交流中心。许多著名的学者，甚至连得伽利略（Galileo，1564—1642），也经常在这里聚会，讨论各类学术问题。其实，梅森所主持的米尼姆修道院，就是法国科学院的前身，以后西方数学及科学的腾飞，事实上都是从这个修道院开始的。
2，从梅森合数的分解说起。
如果说1732年，欧拉给出费马合数2^25+1的一个因子为641，是毫无章法可言的。那么1750年，他所给出的对于梅森合数的判别法则，还是有些价值的，只是对于其中的许多重要的算理没有解释清楚，更没有将这些重要的算理予以推广出去。欧拉发现，如果q为4k-1形素数，那么当2q+1为大于3的素数时，Mq必定可以被2q+1整除。例如，对于q=11，23，83，131，179，191，239和251，分别有因子23，47，167，263，359，383，479和503。
应该说，梅森合数的分解，只是同周期分解里的一种而已。同周期分解具有许多不同的类型，在奇素数生成的各层各阶里，全都含有同周期分解的问题。如果p=2q+1是一个素数，那么2在这个素数里的周期只能是奇素数q，只能是其一个亚根，不可能是其一个原根。因为若要想使2为其一个原根，它的周期就必须是2q，这样就使得这个素数p，变成了1层的素数，而不再是0层的2的周期为奇数的素数，当然只是不可能的。
显然，2q-1是一个大于p=2q+1的数，奇素数q越大，它们之间的大小悬殊就越大，因此，2q-1除了具有素因子p=2q+1之外，必定还会含有许多其它的素因子，而这些素因子里的2的周期，必定是其奇指数q的因子数，由于q是一个奇素数，不存在1和其自身之外的其它的因子数，所以，2q-1除了具有素因子p=2q+1之外，另外所含有的其它的素因子，它们的2的周期，必定也是其奇指数q，这就是形成同周期分解的根源所在。
其实，对于2q-1来说，当指数q是一个较大的奇素数时，如果p=2rq+1是一个素数，那么这个p=2rq+1也可能整除2q-1，形成一个同周期分解。例如229-1=233×2304167，其中233=23×29+1，2304167=2×29×39727+1，都是2的周期为29的素数。另外，我们还可以将对于2q-1梅森合数的同周期分解，推广应用到对于0层，一般2 v-1（v为奇数）形数的分解。例如235-1=31×71×127×122921，其中71=2×35+1，122921=23×35×439+1，都是2的周期为35的素数。
特别需要指出的是，0层各阶的同周期分解，还可以引申到其它各层各阶的同周期分解。所谓的费马数，实际上就是其它各层的0阶数，也是这些层的公因子，它们从第六层开始，都是可以分解的，当然也是属于同周期分解。一般说来，数值范围越大其中的同周期分解，就越为普遍，所分解出的同周期素数的数量也越多。
3，同周期分解的算法。
1903年10月，在纽约展开的美国数学会（AMS）的一次学术会议上，按照会议的议程，哥伦比亚大学的科尔(cole，1861—1926)教授马上要宣读一篇关于整数分解的论文。然而，他一言不发，只是在黑板上写下了：267-1=193707721×761838257287。他说他花了三年的周末时间，才是得到这个分解的。其实，法国数学家卢卡斯(Lucas，1842—1891)，早在1870年就已经检验出，267-1是合数了。
由于一个合数的同周期分解极其困难，因此有人将它运用于密码编制，发明了所谓的公钥密码体制，从而迫使世界各国不得不重视对于同周期分解的研究。笔者对于梅森合数的分解不仅也作过一些深入，而且对于任何合数的彻底的分解，也是有所新的发现。因此，这是一种万能的分解方法。当然，这个万能的分解方法，也只能在我们现在的电子计算机时代，才能予以应用。希望会编程的网友，能根据我下面的算法，编制出一套关于大数分解的实用软件来。
如果m是一个素数，那么在Hm素数域里，只有1和m-1二个元素的二次剩余为1。若是m=qp是二个素数的积，那么在Hm合数环里，除了1和m-1二个元素的二次剩余为1之外，t1≡〈1，-1〉（modqp）和t2≡〈-1，1〉（mod qp）两个同余式组的二次剩余也为1，也就是说，它们会有22个元素的二次剩余为1。因此，我们只要根据t12≡t22≡1（mod qp），即可迅速地找到t1或t2，若t1＜t2，则在t1-1的因子数里必定有q，在t1+1的因子数里必定有p。当然，我们也可以通过t2来计算，那么此时在t2+1的因子数里必定有q，在t2-1的因子数里必定有p。例如，对于211-1=2047来说，由于6222=189×2047+1，因此，也会有（2047-622）2=992×2047+1。由于622-1=27×23，622+1=7×89，于是得到211-1=2047=23×89。
如果m=p1p2…pn是n个素数的积，那么在Hm合数环里，就会有2n个元素的二次剩余为1。我们只要根据这2n个元素，按照上述方法，即可将m=p1p2…pn分解成，2n组两两不同的乘积。由于其中必定会出现，n组一个素数与其它n-1个素数之积的积，因此我们就将m=p1p2…pn予以彻底分解。

bmxskb

没看明白，分解下 685651 看看

n123zj3

看不懂，慢慢看，细细想，我的胃癌已经扩散，没有精力给你解决具体问题。

ucb

楼主，对于一个500位的大数，有什么算法可与快速找出二次剩余为 1 的数？ 不会用每个数去试吧？

n123zj3

应该编制一套这方面的程序，通过电脑去具体计算。