素性检测与整数分解

无心人

能对一些小数字做下示例么？
比如分解3*7*257*9973

福娃PNP

你提出的问题，我目前不具备条件，你可以自己编程，我是在http://wims.math.leidenuniv.nl/w ... ession=690DAB90D1.1这个网站算的，连分数只能算到五百个,如果用你给的数字,无法算出渐进分数,很抱歉,不过你可以在函数计算值这个选项里计算一下你给我的连分数时间复杂度,及GNFS的复杂度,作个比较!

mathe

40#已经给出计算连分数的近似时间复杂度，从中我们看出时间复杂度要大于$O(sqrt(n))$,也就是说，如果采用这种方法，比试除法还要慢，当然更加不用同其他先进的方法去比较了。

无心人

我晕了
我给的数字，如果你不能计算出连分数
那证明你还不具备开解这个问题的能力

计算$N$的根式的连分数只需要精度为$1/N$的浮点精度就可以了
具体到我说的那个数字。双精度double足够计算出所有循环节

wsc810

楼主的问题其实质是解二次同余式 x^2=1   ( mod  b ), 但当b是一个合数是，并没有好的方法，希望楼主另辟溪径

winxos

原帖由 无心人 于 2008-5-21 20:31 发表


能对一些小数字做下示例么？
比如分解3*7*257*9973

这个数连分数到没有多大，循环部分长度2562。

winxos

原帖由 福娃PNP 于 2008-5-22 21:13 发表
你提出的问题，我目前不具备条件，你可以自己编程，我是在http://wims.math.leidenuniv.nl/wims/wims.cgi?lang=cn&+session=690DAB90D1.1这个网站算的，连分数只能算到五百个,如果用你给的数字,无法算出渐进分数,很抱 ...

我帮你写了个连分数计算的程序，可以算19位以内的连分数，比如算根号987654321987654123的连分数，长度有8千多万位，生成的结果有168M多(耗时27s) ，
算根号123456789123456789连分数有300多万位（耗时小于1s），
很难想象你可以用这些数据进行整数分解。。。
不过还是希望我的程序对你有帮助
花了我不少时间，收一个金币是应该的哈。

wsc810

在$sqrt(D)$的连分式分解过程中，用到如下公式
$P_1=0,Q_1=1,a_1=[sqrt(D)]$
$P_2=a_1,Q_2=D-a_1^2$
$P_n= a_(n-1)Q_(n-1)-P_(n-1), $  (1)
$Q_n=(D-P_n^2)/Q_(n-1)$           (2)

$a_n=[(a_1+P_n) /Q_n]$                (3)
其实（2）式不必算$P_n $的平方，便可以得到 $Q_n$的值，
有  $Q_n=Q_(n-2)+a_(n-1)(P_(n-1)-P_n)$
其推导过程如下
  将（2）式中的 $P_n$用（1）式替换
有 ，$Q_n =(D-(a_(n-1)Q_(n-1)-P_(n-1))^2)/Q_(n-1)$
                   $ =[D-(a_(n-1)^2Q_(n-1)^2+2a_(n-1)Q_(n-1)P_(n-1)-P_(n-1))^2]/Q_(n-1)$
                   $=Q_(n-2)+a_(n-1)[-a_(n-1)Q_(n-1)+2P_(n-1)]$   再利用
    $ -a_(n-1)Q_(n-1)=-P_n-P_(n-1) $ 代入得
      $Q_n=Q_(n-2)+a_(n-1)(P_(n-1)-P_n)$，这就是为什么  （2）式，分子能被整除 恒得整数的原因
我想以上方法可以提高计算sqrt(n)连分式的速度

winxos

原帖由 wsc810 于 2009-4-30 21:10 发表
在sqrt(D)的连分式分解过程中，用到如下公式
P_1=0,Q_1=1,a_1=[sqrt(D)]
P_2=a_1,Q_2=D-a_1^2
P_n= a_(n-1)Q_(n-1)-P_(n-1),   (1)
Q_n=(D-P_n^2)/Q_(n-1)  (2)

a_n=[(a_1+P_n) /Q_n]                (3)
其 ...

直接用的以前写的算法，现在我都不记得了。。。
谢谢wsc810，有时间的话我用你的方法写写对比一下。