CTFで使う数学　前編 - CTFと共に生きる

どうも。duckです。
とあるCTF（後で書きます）の過去問解いてたんですが、あまりの数学のできなさに絶望したのでまとめます。
証明は適当につけたのであってるかわかりません。（オイ）
まあわかるっしょっていう条件は書いてなかったり厳密性を重視してなかったりするのでお気を付けくださいませ。
あと個人的にCTFで使う頻度（五段階評価）も書いておきます。まあまだ全然解いてないのであてにはならないですが。
じゃあこっから数学れっつごー。

１．合同式　頻度「５」
ないと死ぬ。Cryptoは整数論でできているのです。
いちいち説明する気にならないので
合同式の意味とよく使う６つの性質 | 高校数学の美しい物語ここらを見ていただければ。

そのうちまとめます。勉強会とか開いたら。（開くとは言っていない）

２．ユークリッドの互除法　頻度「３」

定理： $a,b \in \mathbb N$ の最大公約数は簡単に求められる

詳しいアルゴリズム書くのはめんどいからコード見て。これで $a,b$ の最大公約数が求まります。

def gcd(a,b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

定理の核： $\gcd (a,b) = \gcd (bk + r,b) = \gcd (r,b)$
ただし $a = bk + r(0 < r < a)$

コメント：最大公約数が簡単に計算できることくらいは知っておいたほうがよい。
アルゴリズムは調べれば出てくるし上のコードコピペしてもいいし、お好みで覚えて。

３．拡張ユークリッドの互除法　頻度「４」
RSA暗号に出てくるじゃん。つまり超重要。

定理1： $ax + by = \gcd (a,b)$ の整数解 $(x,y)は計算できる$

これはユークリッドの互除法から構成的に証明できるんだけど、めんどい。
汚いコードおいとくね。（拡張ユークリッドの互除法が入ってるpythonモジュールなくない？）

def extend_gcd(a,b):
    k_list=[]
    while b != gcd(a,b):
        r = a % b
        k_list.append((a - r) // b)
        a = b
        b = r
    k_list.reverse()
    y = 1
    x = 0
    for k in k_list:
        temp_y = y
        y = x - k * temp_y
        x = temp_y
    return [x,y]

ちなみに上のgcdのコードと一緒に使わないと動かないよ。

暗号的には次の応用が重要。（先にいえ）