math314のブログ

主に競技プログラミング,CTFの結果を載せます

任意modでの畳み込み演算をO(n log(n))で

http://misawa.github.io/other/fast_kitamasa_method.html を見て刺激されたので書いた.

  1. 畳み込み演算?
  2. 任意modでの畳み込み演算
  3. 中で使われてる技術達
  4. c++のコード

コードと原理の説明をちょっとだけ載せています.

コードだけ欲しい人は https://gist.github.com/math314/6a08301b8b75b8172798 をどうぞ. fast_int32mod_convolution を使うとint32の任意のmodが取れます.

実はまだverifyしてない.

続きを読む

SECCON CTF 2014 決勝戦 サーバ六 write-up

SECCON CTF 2014決勝戦・全国大会カンファレンス

チーム Mr.Takedashi(メンバー: @misodengaku, @aki33524, @chibiegg, @__math) で出ていました. 9/24位です. 日本人チームの中では4/13位でした.今年はcryptoがあったので幾つか問題が解けました.

他のメンバーのwrite-upです

SECCON 2014全国 - aki33524の日記

SECCON CTF 2014 決勝戦 参加記 « chibiegg日誌

SECCON 2014 全国大会に出た - misodengakuのブログ

去年も決勝大会(http://math314.hateblo.jp/entry/2014/03/03/210318)に出たのですが,順位が下の方で悔しい思いをしました.2014年も出れたなら1桁の順位をとろう!とチームで言っていたので,目標が達成出来て満足です.

私は主に サーバ六 の問題を担当したので,簡単にwrite-up を書きたいと思います.

続きを読む

dwangoプログラミングコンテスト

Welcome to dwangoプログラミングコンテスト - dwangoプログラミングコンテスト | AtCoder

26位でした.D問題が通せなかったの悲しいですね.

最近開催された大会

  • ICPC アジア地区予選 日本地区 2014
    • チーム kyutOUki で出ていました.11位でした.入賞だそうです.
  • CODE FESTIVAL2014
    • 21位でした,賞金が20位からだったので悔しかった.
    • しかしアジア決勝(!?)に出場できるとの事なので,そこで賞金を得たい.
    • Tシャツ2枚,パーカーを貰いました
  • CODE RUNNER 2014
    • 8位でした. 初の賞金だったので嬉しかったのですが,交通費の関係で赤字になりました.
    • もう少し戦略を練れば3位は取れていたので,次回があれば3位以上を目指したい.
    • Tシャツ,パーカーを貰いました

tkbctf4 簡易writeup

rcrypto

M2 + MB_1 = x, M2 + MB_2 = y (mod N)

という式があるので,Mを求めよという問題.

(1つ目の式)y - (2つ目の式)x = 0 より

(y-x)M2 + (B_1 * y - B_2 * x) M = 0 (mod N)

gcd(M,N) = 1 じゃないと困るので(複合できないし)

\[ (y-x)M + (B_1 * y - B_2 * x) = 0 \]

また, gcd(y-x,N) = 1 だったので

\[ M = (B_2 * x - B_1 * y) * (y-x)^{-1} (mod N) \]

後は代入するだけ.

high-low

次の手が分からないと仮定した場合,最適な戦略で挑んだとすると,1回でもクリア出来る確率が63.2%を超えるのに必要な試行回数は132020回程です.頑張ってください.

amida

これでstage20まで行きました.

https://gist.github.com/math314/24a458d0ffc006d151ff

最後のフラグを投げる前に終わってしまいました.

The flag is "Gh057 in the 1egs, not 5hell!"