フト思ったんだが、RSAって任意の素因数分解の話しじゃないだろ。
二つの素数を掛け合わせた合成数だと分かっている上での素因数分解もNP完全かどうか分からないのかね?