今日は2問．関連する話なので．
なぜ「35を素因数分解せよ」は「問題」じゃないの?
35でも，一千万桁を超えるような合成数でも*1，何らかの方法でその個別問題の答えを求め，記録しておけば，あとは同一の個別問題が出たら，記録していたのを書き並べるだけだからです．
ここから「問題を解く手間は，その問題に属する，有限個の個別問題を解く手間から測るものではない」というアドバイスが引き出せます．「1個」から「有限個」に拡張しましたが，それでも，前処理をするか，先人が出した解答を記録しておき，個別問題が来たら適切な答えを返すだけで，実質的な計算をせずに「解が求められた」ことになってしまいます．
512ビットの暗号解読だって有限長じゃないの?
はい，「512ビット」と固定すると，有限個の個別問題になるので，上のアドバイスが確かに適用されます．そういう意味で，「512ビットの暗号解読」は，計算理論では「取るに足らない」と言えそうです．もちろん実用上は，そんなことないのですが．
このケースでは，全通りの答えを覚えることができるかwhether all the answers are storedを，考えないといけません．大雑把な見積もりとしては:
先生「宇宙全体の原子に番号を振るとしても，300ビットも要りませんよ」
(プログラマの数学, p.202)
RSAは512ビットのすべての空間(ビット列)で鍵になり得るわけではないことを引いても，暗号解読の個別問題とその解のペアを全て記憶するのは無理そうです．
次に，解を全て求めて記録するのが無理なら，「個別問題に対して解を計算するプログラム」を作って，個別問題と解の組からなる情報を圧縮できればいいのですが…って，これは，通常我々がやっている「プログラミング」そのものですね．
そういうプログラムを作ると，時間計算量，すなわちそれで解が出るまでにかかる時間がうんと大きくなるか，空間計算量，すなわち解を求めるために必要なメモリサイズがうんと大きくなります．
そうそう，各個別問題について，「解そのもの」ではなく「解くプログラム」を用意しておく，というのも，プログラムコードを格納しておくメモリが個別問題の数に比例して，512ビットの暗号解読ともなると，それが途方もない量になります．単一のプログラムAがあって，個別問題を受け取ったときに，それを解くプログラムBを生成できればいいのですが，あいにくそんなプログラムAは見つかっていません．
*1:今のところ知られている最も大きな素数は，2の32582657乗マイナス1で，980万桁とのこと: http://hg.seoparts.com/dir/en.2ewikipedia.2eorg/wiki/Mersenne_prime
