《连分数法我们知道利用勒让德方法的一个大困难就是寻找形如x2》由会员分享，可在线阅读，更多相关《连分数法我们知道利用勒让德方法的一个大困难就是寻找形如x2（2页珍藏版）》请在金锄头文库上搜索。
1、6连分数法我们知道，利用勒让德方法的一个大困难就是寻找形如x2=a2(modn)的同余式的非平凡解.如果我们可以找到一系列二次剩余：a/三c1(modn),a2k=Ck(modn),而且恰巧ciCk是一个完全平方数.设a=aick,b2=cCk,则有a2=b2(modn),若ab(modn),则就找到了同余式x2=(modn)的一个非平凡解.但这里又出现两个困难：其一，怎么产生这么多的二次剩余呢？其二，哪些二次剩余之积恰好是个平方数？到1931年，勒默和泡尔斯首次用连分数解决了这两个困难，但是，因为当时还没有电子计算机，计算速度的缓慢使得这个连分数方法不被人们注意，直到1975年，莫利桑和卜利
2、尔哈特，对勒默的方法作了深入的研究，将其发展成为一个较系统的好算法，并用此方法，在计算机上成功地分解了屡功不克的F7=227+仁2128+1,从此以后，连分数法就被人们广泛应用于分解因子.到目前为止，它被认为是最有力的分解工具之一.用它可以方便地在计算机上分解50位左右的数.下面，我们对此方法作一介绍.由连廿数的简单性债知；若辰的连分數展开丸为1斬+r3-+令A为它的似肅近分甄这时.有毗-凶醴=(-C4LQm,其中Qm可由一个可以简单计算的递归关系得出.因为对每个m,珂三-“山両切即(-1)-+lQi4l)就是一列一”汝剩余(modn),所以，这样就解决了第一个问题.现在来讨论第二个问题的解决
3、方法.从上列模n的二次剩余(-1)m+1Qm+1中,哪些二次剩余可以选出来成为一个集合使得其元素之积正好是一个完全平方数，从而得到形如x2三c2(modn)的一个非平凡解.我们先看一个例子.例分解n=12007001.对/;展成连分數，秫們得到下晟tn0I112?3340(-j“八毎*131X-11.11*这时将第0,11,27,33,40个同余式肌hQl(-0(me如A；严务(mc-ifl),AIj-Qb.Af产Q工砂為)Aj0=C-0Q*lmodrO乘起秦”得到CA(A1J=2U?J*713*$77=(2f-31*71*97)1*另一方面，用连分数的渐进分数的递推公式，可以计算出A。，A1
4、1,A27,A33,A40，从而可以算出A0A11A27A33A40=9815310(modn),因而，由勒让德的方法可求出n的因子：(9815310-29317197,12007001)=3001，即3001|12007001。从上例可见，要确定哪些（1）m+1Qm+i入选，先要将（-1）m+1Qm+1在某个确定的素因子（包括1）集上分解，再将这些分解了的（1）m+1Qm+i拼凑。这里，在某个集上分解是指在这个集中的因子全部分解出来。我们称上面那个确定的素因子（包括1）集为分解基集。因为，若Pl（1）m+1Qm+1，贝UA2m-knBm2三（1）m+1Qm+1-0nb心）.叫学=1我山因此.
5、分解基集中包括的素数p应復使得算=琢环.国为对凿J尽善大鯛不会起过屁的分解仍然是件麻烦的事情。因而，分解基集中的素数不宜取得太大太多。通常，按需要，指定一个素数Pm，使得分解基集中的素数小于Pm。有时，为了加快算法执行的速度或为了更有可能找到合适的一组二次剩瓠分解基葉中也可以包括一些九十pj旦水于謀的景乩取定一个分解基集，若一个（1）m+1Qm+1的素因子全在这个分解基集中，则称它在这个分解基集上可完全分解，也称它为（对这个基集的）B_数。设分解基集的元素是P0=1和一系列素数P1,P2,，Ph，这时，每一个B_数可以表示为一个二元数组（即Z2h+1中的元）。若（1）m+1Qm+1=P0UP1
6、U1Phuh，则表（1）m+1Qm+1为（e（u。）,&g”,c2）其中r弋,囂票这时两牛B_数之积的表示就是两个B_数的表示之和。若干个B_数之积为平方数等价于说它们对应的表示之和为（0,0,，0）若有g个（在实际应用中，通常取g=h+2）B_数，设为c1，-cg，则可产生一个二元数组成的矩阵，这个矩阵的第i行为ci的二元数组表示，因而，这个矩阵有g行，h+1列。当gh+1时，其行向量（诸q的表示！）就必然对Z2线性相关。因此，有若干个行使其行向量之和为（0,0,，0）（注意到Z2中唯一不为零的元只有1）这样一来，这若干个行对应的B_数之积就是一个完全平方数因而，第二个问题就得以解决了.在连
7、分数算法中，计算量主要是在分解诸（1）m+1Qm+1上计算机往往在不太可能在基集上分解的（1）m+1Qm+1上耗费很多运算波门伦斯对此问题作了研究后，他找出了一个方法，用此方法可以排除那些不太可能在基集上分解的（1）m+1Qm+1他的方法更进一步提高了连分数法的速度.有时，在给定的基集上，很多（1）m+1Qm+1不太可能被分解以致于能分解的（1）m+1Qm+1不够用，波门伦斯的方法可以让计算机尽早回头扩充基集.有时会发生这样的情况：尽管我们由一组B_数乘起来得到了一个完全平方数，但它却导出二次同余式的一个平凡解.这时，我们可以找另外一组B_数来试验，若仍然屡次失败，则可以换或扩充分解基集以得到更多的、更合适的B_数，或换另外的k值再重复试验，直至成功。莫利桑用连分数得到的F?分解式是F7=59649588127497215704689200685129054721最后提一下，波门伦斯对连分数方法作了一个分析，他证明了，连分毀算法旳平均新近工作益是Q&朴峰wa、追个姥杲是从较高深的算法分析中得到的，这里不多介绍。
