Supercomputer Contest 2004
もう2010年も半分過ぎていますが，6年前に開かれたコンテストの解説．別に運営してた人間でも，参加者でもありません．
とりあえず問題の概要は
白黒画像データに対し，とある暗号化処理をかけた画像がある．また，解読のヒントになるある程度の情報もある．このとき，元の画像をどの程度修復できるか？
という感じで，参加者はほぼ全員ヒントを元にした総当りに近い解答をしているみたい．
が，しかし，暗号化方式が RSA であり，その合成数のサイズが 100bit 程度なら因数分解できるんじゃなかろうか？と思って 2 日頑張ってプログラムしてみた流れが以下のとおりである．というか今更日記にするくらいなんだから競技で勝った人と同じ方法やっても面白くない．どうせ理論的に 100％ 正解があり得るんならそれを狙わねば，という思いで書いてます．
まぁ結果として「計算量パネェ」という事になれば今更解説書く必要はないわけで，アッサリ解けたわけです．ノートPC１台で．
ということで具体的な解答手順に行きましょう．そうしましょう．
計算の準備
コンテスト参加者に対してはいろいろデータやらプログラムのパーツやらが配られていたらしいが，コンテストサイトではその辺が配布されていないのでとりあえず必要なデータやらパーツやらを作りました．
まずは正解を確認するための画像…を 0／1 に変換したもの．サイトでは JPEG ファイルしか無いので BMP に convert かけたあとプログラムで 0／1 に変換しました．
次は符号無し 128bit 整数構造体や問題読み込みなどの準備．問題詳細を書いている PDF の 4〜5 ページにいろんな仕様と API が書かれているので，適当に中身を書きましょう．mmul() やら madd() は若干面倒いです．
ここまでで 1 日．ようやく参加者のスタート位置に並ぶ．
アルゴリズムの選択
など方法がいろいろありますが，今回は
という理由からρ法を選びました．
細かく言うと，そもそも 128 bit を超える多倍長が必要無い方法がρ法か試し割り法しか残らないため，理由１の時点でもう２択となりますが，50 bit 分の演算は 1015 にもなるため，神戸の「京」レベルのマシンでないとクリアできません．
ρ法入門
は，実は４年前の d:id:peria:20061113 に書いていたらしいのでリンクするだけ．
ρ法発展
ρ法はモンテカルロ法という別名が表すように，そもそも分解が成功するか，成功するまでの計算量がどうなるか，はデータ依存で，初期値や計算関数によってはいくら計算しても分解できない場合もあります．
そのため，本質的な実装としてはループ回数に適当な上限を設け，初期値や計算数列を乱数でバラして再計算する必要があります．
あとは計算量の削減のために GCD を取る回数を減らすと幸せになります．具体的にはこんな感じ．
def main(n) : while true : p = rho(n) if 1 < p and p < n : return p def rho(n) : x = rand() % n # 初期値を乱択する c = rand() % n # 定数項を乱択する for ek in range(0, 10) : k = 2 ** ek y = x for i in range(1, k) : x = (x * x + c) % n for i in range(1, k) : x = (x * x + c) % n p = gcd(abs(x - y), n) if 1 < p and p < n : return p x = (x * x + c) % n return 1 # 分解できなかったとき
実装とマニュアル風
もう解説を書くのが面倒なので解説は一旦終了．
以上に書いた内容を実装し，さらに MPI で並列化したプログラムやら何やらを supercon2004.tb2 に置いたので遊びたければ使って下さい．ファイルは bzip2 で圧縮しているので
$ tar xjvf supercon2004.tb2
で解凍できます．ファイルに含まれるデータのうち earth.* は本番用問題？のデータで，monkey.* は練習問題らしいです．何故か練習問題は A と C しかないですが，出来上がる画像は一緒(マントヒヒ)のようです．MPI をコンパイルできる環境やら何やら整っている前提で，
$ make # 本番用問題を解く $ make A # 練習問題 A を解く $ make C # 練習問題 C を解く
のどれかでコンパイルして，対応する問題を解いてくれます．
その際，計算し暗号を解読した結果は，計算にかかった実時間 XX.XXXXXX を使って answerXX.XXXXXX.txt というファイルに保存します．解答との整合性チェックが微妙に 100％ になっていないのは，元画像が JPEG だったり，256x256 じゃなかったりしていたせいだと思います．きっと．
実験結果
私の環境としては当時の東工大のスパコンと同様なもの…も使えなくもないですが，MacBook Pro でやりました．2.4GHz の Core 2 Duo なので 2 並列でやりました．メモリは多分全体でもキャッシュに収まるでしょうから無視．4 回実験してみたところ，順に 130 秒，732 秒，1041 秒，58 秒となりました．ただ記録に取ったのがこの 4 回だけで残りのものを消してしまいましたが，印象としてはコンテスト制限時間である 180 秒を切るものが 3，4 割くらいあったと記憶してます．
2 コアのノート PC でこんな感じなので，コンテスト環境の 64 並列ならばほぼ制限時間内に収まると思います．モンテカルロ法なので確定的なことは言えませんが．
ということでザッと書いた感じですが，気が向けばいつか追記するかもしれません．
