连分数法我们知道利用勒让德方法的一个大困难就是寻找形如x2
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的二次剩余{(－1m＋1Qm＋1}中，哪些二次剩余可以选出来成为一个集合使得其元素之积正好是一个完全平方数，从而得到形如x2≡a2(modn的一个非平凡解．我们先看一个例子．
例分解n=12007001．
这时将第0，11，27，33，40个同余式
另一方面，用连分数的渐进分数的递推公式，可以计算出A0，A11，A27，A33，A40，从而可以算出 