6．连分数法 我们知道，利用勒让德方法的一个大困难就是寻找形如x2≡a2(modn)的同余式的非平凡解．如果我们可以找到一系列二次剩余：a12≡c1(modn)，…，a2k≡ck(modn)，而且恰巧c1…ck是一个完全平方数．设a=a1…ak，b2=c1…ck，则有a2≡b2(modn)，若a±b(modn)，则就找到了同余式x2≡a2(modn)的一个非平凡解．但这里又出现两个困难：其一，怎么产生这么多的二次剩余呢？其二，哪些二次剩余之积恰好是个平方数？ 到1931年，勒默和泡尔斯首次用连分数解决了这两个困难，但是，因为当时还没有电子计算机，计算速度的缓慢使得这个连分数方法不被人们注意，直到1975年，莫利桑和卜利尔哈特，对勒默的方法作了深入的研究，将其发展成为一个较系统的好算法，并用此方法，在计算机上成功地分解了屡功不克的F7=22＋1=2128＋1，从此以后，连分数法就被人们广泛应用于分解因子．到目前为止，它被认为是最有力的分解工具之一．用它可以方便地在计算机上分解50位左右的数．下面，我们对此方法作一介绍． 7 Qm，其中Qm可由一个可以简单计算的递归关系得出．因为对每个m， 剩余(modn)，所以，这样就解决了第一个问题． 现在来讨论第二个问题的解决方法．从上列模n的二次剩余{(－ 1)m＋1Qm＋1}中，哪些二次剩余可以选出来成为一个集合使得其元素之积正好是一个完全平方数，从而得到形如x2≡a2(modn)的一个非平凡解．我们先看一个例子． 例 分解n=12007001． 这时将第0，11，27，33，40个同余式 另一方面，用连分数的渐进分数的递推公式，可以计算出A0，A11，A27，A33，A40，从而可以算出A0A11A27A33A40≡9815310(modn)，因而，由勒让德的方法可求出n的因子：(9815310－29·31·71·97，12007001)=3001，即3001|12007001。 从上例可见，要确定哪些(－1)m+1Qm+1入选，先要将(－1)m+1Qm+1在某个确定的素因子(包括－1)集上分解，再将这些分解了的(－1)m+1Qm+1拼凑。这里，在某个集上分解是指在这个集中的因子全部分解出来。我们称上面那个确定的素因子(包括－1)集为分解基集。因为，若p｜(－1)m+1Qm+1，则A2m-knBm2≡(－1)m+1Qm+1 的分解仍然是件麻烦的事情。因而，分解基集中的素数不宜取得太大太多。通常，按需要，指定一个素数pm，使得分解基集中的素数小于pm。有时，为了加快算法执行的速度或为了更有可能找到合适的一组二次剩 取定一个分解基集，若一个(－1)m+1Qm+1的素因子全在这个分解基集中，则称它在这个分解基集上可完全分解，也称它为(对这个基集的)B_数。设分解基集的元素是p0=－1和一系列素数p1，p2，…，ph，这时，每一个B_数可以表示为一个二元数组(即Z2h+1中的元)。若(－1)m+1Qm+1=p0u0p1u1…phuh，则表(－1)m+1Qm+1为(e(u0)， B_数之积的表示就是两个B_数的表示之和。若干个B_数之积为平方数等价于说它们对应的表示之和为(0，0，…，0)若有g个(在实际应用中，通常取g=h＋2)B_数，设为c1，…cg，则可产生一个二元数组成的矩阵，这个矩阵的第i行为ci的二元数组表示，因而，这个矩阵有g行，h ＋1列。当g＞h＋1时，其行向量(诸ci的表示！)就必然对Z2线性相关。因此，有若干个行使其行向量之和为(0，0，…，0)(注意到Z2中唯一不为零的元只有1)这样一来，这若干个行对应的B_数之积就是一个完全平方数．因而，第二个问题就得以解决了． 在连分数算法中，计算量主要是在分解诸(－1)m+1Qm+1上．计算机往往在不太可能在基集上分解的(－1)m+1Qm+1上耗费很多运算．波门伦斯对此问题作了研究后，他找出了一个方法，用此方法可以排除那些不太可能在基集上分解的(－1)m+1Qm+1．他的方法更进一步提高了连分数法的速度． 有时，在给定的基集上，很多(－1)m+1Qm+1不太可能被分解以致于能分解的(－1)m+1Qm+1不够用，波门伦斯的方法可以让计算机尽早回头扩充基集． 有时会发生这样的情况：尽管我们由一组B_数乘起来得到了一个完全平方数，但它却导出二次同余式的一个平凡解．这时，我们可以找另外一组B_数来试验，若仍然屡次失败，则可以换或扩充分解基集以得到更多的、更合适的B_数，或换另外的k值再重复试验，直至成功。 莫利桑用连分数得到的F7分解式是 本文来源：https://www.wddqw.com/doc/47d79c08cd22bcd126fff705cc17552707225e95.html