素因数分解は，NP完全問題でしょうか？

質問

タイトル通りです．

素因数分解はNP完全問題でしょうか？　それとも，クラスNPに属するだけでしょうか？

ド素人ですのでできるだけ解り易くお願いいたします・・・．

回答No.1

ur2c · ベストアンサー

http://www.cs.gunma-u.ac.jp/~nakano/Algo/npc.html
をご覧ください。

お礼

ありがとうございます！！