ksnctf #20 G00913

問題

http://ksnctf.sweetduet.info/problem/20

考えたこと

問題文に FLAG_Q20_{first 10-digit prime found in consecutive digits of π} とあったが、そもそもG00913ってなんだよ聞いたこともないぞと思い、タイトルをググった。そうすると、下の写真が出てきた。これはgoogleの求人広告らしい。どう見てもこれをオマージュした問題である。答えそのものはググったときについでに出てきた。

おまけというかついで

これまたこいつをオマージュした問題でYet Another G00913という問題もある。

http://ctf.katsudon.org/problem/13

これの厄介なところは200桁を判定しなければならないところである。上の10桁程度ならRubyのPrimeクラスとか使えそうだが、さすがに200桁は無理なので、別の方法を考えないといけない。他のアルゴリズムとして桁が小さければエラトステネスのふるい、フェルマーの小定理(フェルマーテスト)があったりするが、それは疑素数といって素数でなくても通ってしまう数字が出てくる。それを改良しても通ってしまうカーマイケル数というものもあるが、まあ詳しくはググってください(細かく書くのが面倒)。そこで今回用いるミラーラビンテストの登場である。こいつは200桁の素数判定でも一瞬で終わる優れものである。これも確率的素数判定なので間違いが出ることはあるが、その確率は判定回数をk回とすると「4^-k」なので、kを大きくすればほぼなくなる。実装はさほど難しいわけではないが、PHPならgmp_prob_prime()という組み込み関数がミラーラビンの確率的テストによっておそらく素数であるか調べてくれる。この辺のもう少し詳しい話は気が向けばMathIについての記事を書いた時にやろうと思う。