作者reader (读者)
看板CSSE
标题Re: [问题] 关於因数分解
时间Tue Mar 8 13:59:35 2005
※ 引述《Azraelx (胜败乃兵家之常事)》之铭言：
: 一般认为m=p*q, 当p,q是很大的质数时
: 只知道m,是不容易分解出p,q的
: 那n=p*q*r时, 当p,q,r是很大的质数时
: n是不是容易因数分解的啊?
是不是容易分解是相对的。
若 m 和 n 有同样的位数 s
那构成 m 的 p q 之位数，大约接近 s/2 位
而构成 n 的 p q r 则是接近 s/3 位
s/2 自然是大於 s/3.
若 s 为 30, 那麽用暴力法解开 n 和 m, 时间比大约是：
10^15 : 10^10 = 100000 : 1
10 万倍的差距，相对於 m 来说, n 自然是容易分解的了，
这可能就是一小时跟十年的差距。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.222.173.26