>>1
言いたい事は何となく分かった。

まず、既知の素数のリスト(有限)だけではあらゆる素因数分解を行えないため計算可能ではない。
つまり、素因数分解できる保証が無いということだ。

でも必要十分な素数が生成してあるならば、多項式時間で解決できると思うよ。
(素数の数は入力データ長に対して対数オーダーだから)

世界のどこかには膨大な素数を生成しているハッカーが居るのかもね。



暗号解読は面白ね。
俺も一昨年くらいに読んだ。