素性检测与整数分解

福娃PNP · 发表于 2008-5-4 20:48:48

看不懂呀！能不能麻烦您帮我计算一下100位的？

无心人 · 发表于 2008-5-4 21:07:47

$n = 100$时间复杂度大概$5.4828*10^30$

福娃PNP · 发表于 2008-5-5 18:46:10

你公式里的N指的是什么?是指连分数的循环节吗?你说的时间复杂度是指所用的时间吗?你上面算的结果的单位是什么?

无心人 · 发表于 2008-5-5 20:12:00

n指的是待分解数字

无心人 · 发表于 2008-5-5 20:15:01

时间复杂度是个约数，不等于实际时间
估算实际时间要测试的

不过你算下
一台机器每秒做10^16次运算
算未来10年内最快的
那还需要10^14秒，合31.7万年呢

：）

福娃PNP · 发表于 2008-5-7 21:03:34

您的意思是说:如果一台机器每秒做10^16次运算,那么计算一个100位的整数的连分数需要31.7万年?

无心人 · 发表于 2008-5-7 22:23:06

福娃PNP · 发表于 2008-5-13 18:40:12

我是说:求根号N的连分数的时间复杂度,没有讲清楚,你现在告诉我的是连分数法的时间复杂度,所以麻烦您在忙我找一下.即根号N的渐进分数的时间复杂度.谢谢您!

无心人 · 发表于 2008-5-13 18:45:51

哦

那个很快的
应该是o(lgn)算法

福娃PNP · 发表于 2008-5-15 20:02:13

假设我计算一个500位数N的连分数需要多长时间?其实,就是相当于需要知道解不定方程x²-Ny²=1的时间复杂度!

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 素性检测与整数分解