素因数分解の時間

[lbfuvab]

馬鹿なことを聞いているのかも知れませんが、本当に分からないので質問させていただきます。
二つの素数を掛けた合成数nについて素因数分解する場合、
調べなければならないのは[√n]までですよね？([/url]はガウス記号)

なのに何故計算時間が指数関数的に増えていくのかが良く分からないです。
いくら調べても納得がいきません。

どなたか詳しい方教えてください。

[たいちう]

詳しいという程の事もないのですが、何点か回答らしきものを。

まず「計算時間が指数関数的に増えていく」とは、
誰が主張しているのでしょうか？
その主張が間違っている可能性や、「指数関数的」という言葉が
比喩的に使われている可能性があります。

また、合成数nに対してなら数学的な意味での「指数関数的」とは言えなくても、
合成数の桁数（もしくはビット数）nに対してなら「指数関数的」と言えるでしょう。
主張している人の意図はこっちではないでしょうか。

こっから先が私ではついていけない部分なのですが、
どうやら「準指数関数的」というのが正しいらしいです。
興味があれば読んでみてください。
（よろしければ、かいつまんで私に教えてください）

http://slashdot.jp/comments.pl?sid=139683&cid=450555
http://www.rkmath.rikkyo.ac.jp/~kida/bunkai.htm

[sizuma]

僕は今までは

素数の数はほぼ同じぐらいの増加量だと思うので、nが2倍になれば、素数に対しての計算も2倍
でも計算アルゴリズム自体が大きい数になればなるほど時間のかかる処理だとすれば計算は2倍でも計算時間は2倍以上になるハズ。割り算計算が基本だと思うので、計算時間も増加しやすいと思いますし。


・・・って思ってました。
でもたいちうさんの書いてあるみたいに、ビットに対しては指数関数的っていうことなんでしょうね。
大学数学レベルの話になってくると思うんで、僕にも分かるように教えてほしいです（笑

[lbfuvab]

有難うございます。
・・・う～ん、理解できませんorz
しかし、不思議な事に単なる指数関数時間でもないんですね・・・