一个564位大整数分解

mathematica

但是为何放着非常简便的二次多项式不用，偏要用奇特的连分数呢？那是因为这个不等式｜Qi｜<2sqrt(n).数列Qi的绝对值比数列Q(x)要小很多。（当x的值偏离根号n时，数Q(x)的值几乎是线性增长，且斜率为2sqrt(n).)如果一个人要处理很多数，以便从中发现一些数相乘后得到一个完全平方数，大概处理一批较小的数比处理一批较大的数要容易些吧。所以Lehmer与Powers的连分数方法比Kraitchik的二次多项式有一个明显的优点。
https://wenku.baidu.com/view/99e ... d960590c6d98e.html#

mathematica

例如，让我们再考虑数2041并尽力用Kraitchik方法来分解它，但现在允许用负数。这样使用多项式Q(x)=x^2-2041和因子基2,3,和5，我们有      Q(43)=-192=-2^6·3 ←→ (1,0,1,0)     Q(44)=-105      Q(45)=-16=  -2^4  ←→ (1,0,0,0)     Q(46)= 75= 3·5^2 ←→ (0,0,1,0),  这里相关指数的第一个坐标是-1.所以使用包括2，3和5的更小的因子基，但也允许负数，我们很幸运，目前收集到的三个向量是线性相关的。这样就有了同余式(43·45·46)^2≡(-192)(-16)(75) mod 2041,即1247^2≡480^2 mod 2041.这又给出了2041的因子13，因为（1247-480，2041）=13.  最后的求解最大公约数的步骤会得到一个非平凡分解吗？答案是不一定.读者可以试试2041的又一组平方数解集.例如x=41,45和49时,算出Q(x)，最后得到同余式601^2≡1440^2 mod 2041.用前面说的术语，这个同余式是平凡的，因为601≡-1440 mod 2041.这样，可以肯定最大公约数(601-1440,2041)的值是很无趣的因子1.

mathematica

http://www.ams.org/notices/199612/pomerance.pdf
A Tale of  Two Sieves  Carl Pomerance  (This paper is dedicated to the memory of my friend and  teacher, Paul Erdos)