# CTF數學

> Author:堇姬
# 歐拉函數
## 定義
$ϕ(n)$為在所有的正整數當中，有多少$<n$的數字與n互質。
## n=質數 狀況
在這個定義之下，如果說n是一個質數的話，那麼所有$<n$ 的正整數也必定與之互質，因此此時的 $ϕ(n)=n−1$

# 歐拉定理
## 定理內容
若 $n, a \in \mathbb{N}$ 且 $gcd(n,a)=1$
則
$a^{ϕ(n)} \equiv 1 \pmod n$

## 證明
設有一數字 $n$ 其 $ϕ(n)=b$
與$n$互質的數有 $p_1, p_2 ... p_b$
我們可以知道若有一數字 $a$，$gcd(a,n)=1$
那麼 $ap_1,ap_2,...ap_b$仍和 $n$互質

$ap_1 \times ap_2 \times...\times ap_{b-1} \times ap_b \equiv p_1 \times p_2 \times ...\times p_{b-1} \times p_b \pmod n$
提出$a$左右消掉得
$a^b \equiv 1 \pmod n$
$a^{ϕ(n)} \equiv 1 \pmod n$
# 費馬小定理

## 定理內容

a為一個整數，p為一個質數，若gcd(a,p)=1，則

$a^{p-1} \equiv 1 \pmod {p}$

## 證明

設 $x_1$,$x_2$,$x_3$...$x_{p-1}$ 為 1,2,3,4...(p-1)的排列。
>先證 $ax_1$,$ax_2$,$ax_3$...$ax_{p-1}$任兩個對p不同餘
>
**反證法:**
設有`i`、`j`兩數，$1 \leq i < j \leq p-1$，則可以寫成
$ax_i \equiv ax_j \pmod {p}$
$ax_j-ax_i \equiv 0 \pmod {p}$
$a(x_j-x_i) \equiv 0 \pmod {p}$
可知$ax_j -ax_i$可被$p$整除，但gcd(a,p)=1
故$x_j-x_i$被p整除
$x_i \equiv x_j \pmod {p}$ 但$x_i$、$x_j$皆小於p，故任取兩數皆不可能同餘($⇒⇐$)]
故 $ax_i \equiv ax_j \pmod {p}$ 不成立

>所以$ax_i$(i=1~p-1)所有數，皆不同餘。
也就是說$ax_i$(i=1~p-1)對p取餘數的話為1,2,3...p-1(因為有p-1個數)

所以
$ax_1×ax_2×ax_3×...×ax_{p-1} \equiv 1 ×2×3×...×p-1 \pmod {p}$
$a^{p-1}×(x_1×x_2×x_3×...×x_{p-1}) \equiv 1 ×2×3×...×p-1 \pmod {p}$
$a^{p-1}×(p-1)! \equiv (p-1)! \pmod {p}$

故得證$a^{p-1} \equiv 1 \pmod {p}$

# 貝祖定理

## 定理內容

對任何整數 $a$、$b$、$d=gcd(a,b)$
$ax+by=dk$
有整數解時若且唯若 $m$ 是 $d$ 的倍數

若 $ax+by=1$ 有整數解
$a$ , $b$互質

## 證明
分兩種狀況
> a,b其中一數為0

因為$a$或$b$和0的最大公因數都是他自己，得證

# 二次剩餘
當存在一整數 $X$，使$X^2 \equiv d \pmod p$
稱「d是模p的二次剩餘」
# 歐拉準則
## 定理內容
若p是奇質數且p不能整除d，則:

**d是mod p的二次剩餘**

$d^{(p-1)/2} \equiv 1 \pmod p$

**d是mod p的非二次剩餘**
$d^{(p-1)/2} \equiv -1 \pmod p$

# 中國剩餘定理

## 定理內容

$C_1 \equiv m \pmod {n_1}$
$C_2 \equiv m \pmod {n_2}$
$C_3 \equiv m \pmod {n_3}$

可以寫成

$N=n_1 \times n_2 \times n_3$

$K_i= \frac{N}{n_i}$

$m \equiv (C_1K_1K_1^{-1}+C_2K_2K_2^{-1}+C_3K_3K_3^{-1}) \pmod N$

## 實作

import gmpy2
import functools
from Crypto.Util.number import *

def crt(c, n):
    '''
    Input: [c_1, ... c_i], [n_1, ..., n_i]
        x = c_1 (mod n_1)
        x = c_2 (mod n_2)
        ...
        x = c_n (mod n_i)
    Output: x
    '''
    N_ALL = functools.reduce(lambda x, y: x * y, n)
    total = 0

    for Ai, ni in zip(c, n):
        Ni = N_ALL // ni
        total += Ai * Ni * (gmpy2.gcdext(Ni, ni)[1] % ni)

    return total % N_ALL

# 威爾遜定理
## 定理內容
p為質數

$(p-1)! \equiv -1 \pmod p$

# 歐幾里德算法

## 定理內容
兩個整數的最大公因數是能夠同時整除它們的最大的正整數
欲求252和105的最大公因數

252%105=42
a=105 b=42

105%42=21
a=42 b=21

42%21=0

最大公因數21

## python腳本

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

# 擴展歐幾里得算法

## 定理內容
擴展歐幾里得算法可以在求得a、b的最大公因數的同時，找到整數x、y
使滿足
$ax+by=gcd(a,b)$

## python腳本

from gmpy2 import gcdext
GCDNUM, y, x = gcdext(a,b)