作者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