Problem 59 (Project Euler) [原文]
暗号化鍵は3文字の小文字である. cipher1.txtは暗号化されたASCIIのコードを含んでいる. また, 平文はよく用いられる英単語を含んでいる. この暗号文を復号し, 平文のASCIIでの値の和を求めよ.
ちょっとしたハッカー気分でどうぞ。
要は、英小文字3文字からなるパスワードを用意し、先頭バイトからXOR演算を繰り返し行って、文字に復号してみろ…ということです。
まず先頭の何文字か分だけを復号し、「ありふれた英単語」が含まれるか否を確認してパスワードを決定します。全てを復号して答えを求めるのはその後がよさそうです。
最初に何バイトぐらいを復号するか、また「ありふれた英単語」として何を選ぶのかの２点で少し試行錯誤が必要でした。わかってしまえばなんでもないのですけど…。
復号後の"cipher1.txt"はちょっと意地悪な書き出しになっています。
Problem 58 (Project Euler) [原文]
1から初めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.
(中略)
面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は8/13 ≒ 62%である.
渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.
Problem 28で扱った螺旋数列の問題で、手間が省けて簡単かと思いきや、さすがにこのレベルの問題はひとひねりがあります。
「エラストテネスの篩」はせいぜい400万ぐらいまでを用意すればよかろうと思ったら、篩で用意した素数の範囲を超えても、なかなか10%を割りません。
5千万ぐらいまで確保しようとしたところで、当然のことながら、必要なメモリ領域を確保できなくなりました。
やむなく「ミラー・ラビン」でググると、親切にもWikipediaに素数判定用のRubyコードがあったのでコピペしました。敗北感にまみれながら…orz
ミラー-ラビン素数判定法 (Wikipedia)
