7-Number Theory

背景知识

自然数的集合论定义：
- $a^+:=a\cup\{a\}$
- 归纳集
  - $\emptyset\in A$
  - $\forall a(a\in A\rightarrow a^+\in A)$
- $\mathbb{N}$ 为所有归纳集之交
Peano 结构
- $e\in S$
- $\forall a\in S,f(a)\in S$
- $\forall b\in S,\forall c\in S,f(b)=f(c)\rightarrow b=c$
- $\forall a\in S,f(a)\not= e$
- $\forall A\subseteq S, (e\in A\wedge(\forall a\in A)(f(a)\in A))\rightarrow A=S$
良序公理与数学归纳法原理等价

数论基础

带余除法: $a=bq+r,b>0,0\leq r<b$ $a = b q + r, b > 0, 0 \leq r < b$
- 存在性证明：良序公理
- 唯一性证明
整除及其性质
- $a|b,a|c\Rightarrow a|nb+mc$
最大公因子 (hcf/gcd)
- 裴蜀定理： $\gcd(a,b)=ar+bs$ $g cd (a, b) = a r + b s$
  - 证明：良序公理+带余除法
- Strong Duality for GCD: $\max\{d_i:d\in\mathbb{Z},d|a,d|b\}=\min\{ax+by:x\in\mathbb{Z},y\in\mathbb{Z},ax+by>0\}$ $max {d_{i} : d \in Z, d ∣ a, d ∣ b} = min {a x + b y : x \in Z, y \in Z, a x + b y > 0}$
  - 证明
    1. $d|s,s|d$
    2. Weak Duality + $\exists$
  - 唯一性证明
- $\text{lcm}(a,b)\gcd(a,b)=ab$ $lcm (a, b) g cd (a, b) = ab$
  - 证明
    1. Isomorphism Theorem
    2. Unique Factorization
    3. $d|(a,b)\Leftrightarrow d|\frac{ab}{[a,b]}$
  - $(a,b,c)[a,b,c]=\frac{abc}{[(a,b),(b,c),(c,a)]}$
  - $[a,b,c]=\frac{abc(a,b,c)}{(a,b)(a,c)(b,c)}$
- $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$
质数
- $\pi(x)\sim\frac{x}{\ln{x}}$
- 无限质数证明
  1. $P=p_1p_2\cdots p_n+1$
  2. Fermat Numer $F_n=2^{2^n}+1$ $F_{n} = 2^{2^{n}} + 1$ 两两互素
    - $F_n-2=\prod_{k=1}^{n-1}F_k$
  3. Mersenne Number $2^p-1$ $2^{p} - 1$
    - $2^p\equiv 1\pmod{q}\Rightarrow p|q-1$
  - Dirichlet's Theorem: $\gcd(a,m)=1$ then there are infinitely many primes $p,p\equiv a\pmod{m}$
- 筛法求素数
- 算术基本定理
  - 存在性证明：良序公理（找不满足中最小的）
  - 唯一性证明： $1\rightarrow n$
$\varphi(n)=n\prod_{p|n}(1-\frac{1}{p}),p$ $φ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p}), p$ is prime
- $\varphi(p)=p-1$
- $\varphi(n)>\frac{n}{e^\gamma\ln\ln n+\frac{3}{\ln\ln n}},\gamma=0.577$
Additivie group module n: $(\mathbb{Z}_n,+_n)$ $(Z_{n}, +_{n})$
- $\langle a\rangle=\langle (a,n)\rangle$ $⟨ a ⟩ = ⟨(a, n)⟩$
  - $|\langle a\rangle|=\frac{n}{(a,n)}$
Multiplicative group module n: $(\mathbb{Z}_n^*,\cdot_n)$ $(Z_{n}^{*}, \cdot_{n})$
- $\text{ord}(a)$ $ord (a)$ : the smallest possible integer that $a^{(t)}=e$ $a^{(t)} = e$
  - $\text{ord}(a)=|\langle a\rangle|$
  - Primitive root: $a,\text{ord}_m(a)=\varphi(m)$ $a, ord_{m} (a) = φ (m)$
    - Number: if exists, $\varphi(\varphi(m))$
- Euler's Theorem: $a^\varphi(n)\equiv 1\pmod{n}$ $a^{φ} (n) \equiv 1 (mod n)$
  - Fermat's Theorem: $a^{p-1}\equiv1\pmod{p}$
- Wilson Theorem: $(p-1)!\equiv -1\pmod{p}\iff p$ is prime
quadratic residue
- $a$ is quadratic residue $x^2=a\pmod{p}$ has a solution for $x$
- $\frac{p-1}{2}$ quadratic residues for $p$
- Legendre symbol $(\frac{a}{p})=1$ if $a$ is a quadratic residue otherwise $-1$
- $(\frac{a}{p})\equiv a^{(p-1)/2}\pmod{p}$

Modular linear equations

$ax\equiv b\pmod{n}$ $a x \equiv b (mod n)$
- 有解： $d=\gcd(a,n)|b$
- 求解：
  - $ax+bn=d$
  - $x_0=\frac{xb}{d}$
  - $x_1=x_0+i\frac{n}{d},i=0,\cdots,n-1$

CRT (The Chinese remainder theorem)

$n=n_1n_2\cdots n_k$ $n = n_{1} n_{2} \dots n_{k}$ , where $n_i$ $n_{i}$ are pairwise relatively prime, then we have mapping $a\leftrightarrow(a_1,a_2,\cdots,a_k)$ $a \leftrightarrow (a_{1}, a_{2}, \dots, a_{k})$ , for $\cdot=+/-/*$ $\cdot = + / - / *$ , we have $(a\cdot b)\pmod{n}\leftrightarrow ((a_1\cdot b\pmod{n_1},\cdots,(a_k\cdot b_k)\pmod{n_k}))$ $(a \cdot b) (mod n) \leftrightarrow ((a_{1} \cdot b (mod n_{1}), \dots, (a_{k} \cdot b_{k}) (mod n_{k})))$
- $\rightarrow$ : direct
- $\leftarrow$ $\leftarrow$
  - $m_i=\frac{n}{n_i}$
  - $a\equiv(\sum_{i=1}^ka_im_i(m_i^{-1}\pmod{n_i}))\pmod{n}$
一般同余方程
- 法一：
  - 有解： $a_i\equiv a_j \pmod{(n_i,n_j)}$
  - 先拆后合（相同或倍数）
  - $x\equiv a\pmod{n_i}\iff x\equiv C\pmod{[n_1,\cdots,n_k]}$
- 法二：
  - 两两合并
简化计算：
- $2^{300}\bmod 319$
- $319=11*29$ + CRT

数论算法

model: multplying two $\beta$ -bit integers take $\Theta(\beta^2)$ bit operations

Euclid Algorithm

int ext_gcd(int a, int b, int &x, int &y){
    if (b==0) {
        x = 1; y = 0;
        return a;
    } else {
        int ret = ext_gcd(b,a%b,y,x);
        y -= x*(a/b);
        return ret;
    }
}

$a>b\geq 1$ $a > b \geq 1$ and Euclid(a,b) performs $k\geq 1$ $k \geq 1$ recursive calls, then $a\geq F_{k+2},b\geq F_{k+1}$ $a \geq F_{k + 2}, b \geq F_{k + 1}$
- 证明： $a\geq b+(a\bmod b)$
- Lame's Theorem: $k\geq 1,a>b\geq 1,b<F_{k+1}$ then Euclid makes fewer than $k$ recursive calls
- $F_k\sim\frac{\phi^k}{\sqrt{5}},\phi=\frac{1+\sqrt{5}}{2}$
- $O(\lg b)$

Modular Exponentiation

int fp(int a, int b, int mod){
    int c = 1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c%mod;
}

Primality Testing

trial division: $\Theta{\sqrt{n}}$
Pseudoprimality testing:
- base- $a$ pseudoprime: $a^{n-1}\equiv 1\pmod{n}$
- Carmichael numbers: $\forall a\in\mathbb{Z}_n^*,a^{n-1}\equiv 1\pmod{n}$
- Algorithm: return MODULAR-EXPONENTIATION(2,n-1,n) $\equiv 1\pmod{n}$
Miller-Rabin randomized primality test
- $x^2\equiv 1\pmod{p^e}$
- $O(s\beta^3)$
- $n$ is an odd composite number, then the number of witnesses to the compositeness of n is at least $\frac{n-1}{2}$
- $P(\text{MILLER-RABIN errs})<2^{-s}$
- $P(\text{prime}|\text{RETURN prime})>0.5$ $P (prime ∣ RETURN prime) > 0.5$ if $s>\lg(\ln n-1)$ $s > l g (ln n - 1)$
  - applicable: $s=50$

LL multimod(LL a, LL b, LL mod) {
    a %= mod;
    b %= mod;
    LL res = 0;
    while (b) {
        if (b & 1) {
            res += a;
            if (res >= mod) res -= mod;
        }
        b >>= 1;
        a <<= 1;
        if (a >= mod) a -= mod;
    }
    return res;
}
 
bool witness(LL s, LL n) {
    LL u = n - 1, t = 0;
    while ((u & 1) == 0 && u != 0) u >>= 1, t++;
    LL x = fp(s, u, n), tmp;
    while (t--) {
        tmp = x;
        x = multimod(x, x, n);
        if (x == 1 && tmp != n - 1 && tmp != 1) return true;
    }
 
    if (x != 1)
        return true;
    else
        return false;
}
 
bool millerrabin(LL n, const int times = 3) {
    if (n == 2) return true;
    if ((n & 1) == 0 || n < 2) return false;
    int i = times;
    while (i--) {
        LL x = random(2, n - 1);
        if (witness(x, n)) return false;
    }
    return true;
}

Integer factorization

Trial division $R\rightarrow R^2$
Pollard's rho heuristic $R\rightarrow R^4$ $R \to R^{4}$
- initial: $x_1=\text{random}(0,n-1),y=x_1,k=2$
- Loop
  - $x_i=x_{i-1}^2\pmod{n}$
  - if $\gcd(y-x_i,n)\not=1/n$ finded
  - if $i==k$ $i == k$
    - $y=x_i$
    - $k=2k$

Crypotography

Private Key Crypotography

affine cryptosystem: $f(p)=ap+b\pmod{n}$
polyalphabetic crypotosystem
- German ADFGVX Field Cipher
Kerckhoffs's principle

Public Key Crypotography

$f^{-1}$ must be difficult to compute
PKC
- Self $P,D$
- Others $P',D'$
- Message $M$
- 公钥加密
  - encoding with $P'$ : $P'(M)$ -> send
  - receive -> decoding with $D'(P'(M))$
- 数字签名
  - signing with $D$ : $M'=M+D(M)$
  - (encrypt and) send -> receive (and decode)
  - verifying $M=P(D(M))$
RSA
- $n=pq$
- $(E,\varphi(n))=1$
- $DE\equiv 1\pmod{\varphi(n)}$
- public: $(n,E)$
- secret: $(n,D)$
- encoding: $y=x^E\bmod n$
- decoding: $x=y^D\bmod n$
DH(Deffie-Hellman)
- $a$ : small prime
- $p$ : large prime
- Agent a: $(X_a,Y_a=a^{X_a}\bmod p)$
- Agent b: $(X_b,Y_b=a^{X_b}\bmod p)$
- secret key: $K=Y_b^{X_a}\bmod p= Y_a^{X_b}\bmod p$
Attack
- Small $e$ $e$ Attack: $e=3,d$ $e = 3, d$ obtained
  - Result: $p,q$ leaks
  - $ed=1+k\varphi(n),k\in\mathbb{Z},k<\min\{e,d\}$
- Common Modulus Attack: $(e_i,e_j)=1$ $(e_{i}, e_{j}) = 1$
  - Result: if message decoded both sent, original message can be recovered
  - $M=E^xF^y\pmod{n},e_1x+e_2y=1$

Table of Contents

Table of Contents

7-Number Theory

背景知识

数论基础

Modular linear equations

CRT (The Chinese remainder theorem)

数论算法

Euclid Algorithm

Modular Exponentiation

Primality Testing

Integer factorization

Crypotography

Private Key Crypotography

Public Key Crypotography