CINTA重点

根据华南师范大学计算机学院斌头老师的课件整理
整理者：0.H.P

计算机数学

---

可除性和带余除法

定理：

设a,b $\in Z$,$b>0$,那么$\exists q,r \in Z$,使得$a=bq+r$其中$0 \leq r \leq b-1$,且这对整数q,r为上述a,b所唯一确定。

证明：

证明：
(1).证r的范围：
将实数轴分为左闭右开的长度均为b的无穷个小区间，即

$$[nb,(n+1)b),n \in Z$$
可得a必定落在某一区间内，故$\exists q \in Z$,使得$qb \leq a<(q+1)b$.令$r=a-bq$,则$0\leq r<b$，又因为$r \in Z$,故得$r \leq b-1$.
(2).证q与r的唯一性：
首先证a所在区间的唯一性：运用反证法。
假设$a\in [nb,(n+1)b)$且$a\in [mb,(m+1)b)$，其中$n\neq m$,那么假设$n<m$.得$n+1\leq m$
那么假设$\exists x\in [nb,(n+1)b),\exists y\in [mb,(m+1)b)$,那么有：
$$\lim\limits_{x\to max}x<\lim\limits_{y\to min}y$$
故得：a所在区间唯一。又由于$a\in[qb,(q+1)b)$,得q唯一。又a=qb+r,得r唯一。
证毕。

欧几里得算法(gcd)

目的：

求两个数的最大公约数

公式：

$gcd(a,b)=gcd(b,a\ mod\ b)$直到$b=0$

方法：

对于$ab\neq 0$,且$b>0,b \nmid a$,运用带余除法表达式，有

$$a=bq_0+r_0,q_0 \mbox{与} r_0 \in Z,\mbox{且有} r_0\in [1,b-1] \\ b=r_0q_1+r_1,q_1 \mbox{与} r_1 \in Z,\mbox{且有} r_1\in [1,r_0-1]\\ r_0=r_1q_2+r_2,q_2 \mbox{与} r_2 \in Z,\mbox{且有} r_2\in [1,r_1-1]\\ r_1=r_2q_3+r_3,q_3 \mbox{与} r_3 \in Z,\mbox{且有} r_3\in [1,r_2-1]\\ \vdots$$
可得除第一与第二式外，其余都是用后一个余数除前一个余数的余数，即$r_0=a\ mod\ b,r_1=b\ mod \ r_0 \cdots$
以此计算，直到余数为0，即
$$r_{n-1}=r_nq_{n+1},q_{n+1} \in Z$$ $r_{n-1}$即为结果。

证明：

假设$a,b,d,q \in Z$,且不全为0，且有$a=bq+c$.
若a与b的公因数为d,$\Rightarrow d|a$且$d|c \ \Rightarrow d|qb+c \ \Rightarrow d|c$
即d也是b与c的公约数$\Rightarrow gcd(a,b)=gcd(b,c)$
以此计算，有$gcd(a,b)=gcd(b,r_0)=\cdots gcd(r_nq_{n+1},r_n)$
证毕.

时间复杂度：

$log_2n$

递归算法：

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

迭代算法：

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

拓展欧几里得算法(egcd)

目的：

求线性方程组$a*r+b*s=gcd(a,b)$的一组解

方法：

$令q=a//b$

$$\begin{bmatrix} a*r_0 & b*s_0 & a\\ a*r_1 & b*s_1 & b\\ \end{bmatrix} = \begin{bmatrix} a*r_1 & b*s_1 & b\\ r_0-q*r_1 & s_0-q*s_1 & a\%b\\ \end{bmatrix}$$
以此循环

def egcd(a,b):
    r0,r1,s0,s1=1,0,0,1
    while b:
        q,a,b=a//b,b,a%b
        r0,r1=r1,r0-q*r1
        s0,s1=s1,s0-q*s1
    print(a,r0,s0)

---

费马小定理

公式:

p是素数时，$a∈[1,p)$
有$a^{p-1}≡1(mod\ p)$

证明:

取$i,j∈[1,p-1),i≠j$
$令a*i≡a*j(mod\ p)$
由消去律得$i≡j(mod\ p),即i=j,与题设矛盾$
故得$a*i(mod\ p)有p-1种结果$
所以

$$\prod_{i=1}^{p-1}i=\prod_{i=1}^{p-1}a*i=a^{p-1}\prod_{i=1}^{p-1}i(mod\ p)$$
即$a^{p-1}≡1(mod\ p)$

例题:

$p=17,a=3,求a^{2018}(mod\ p)$
解:$p=17,p-1=16$
得$a^{p-1}=a^{16}≡1(mod\ p)$
所以$a^{2018}=a^{16*126+2}=a^2=9$
故$a^{2018}(mod\ p)≡a^2(mod\ p)≡9$

---

欧拉公式

公式：

$a^{φ(n)}≡1(mod\ n)$

证明：

$φ(n)=|{b:1<=b<n\ and\ gcd(b,n)=1}|$
设集合$S=\{b_1,b_2,b_3...b_i:1<=b_i<n\ and\ gcd(b_i,n)=1\}$
$S'=\{a*b_1,a*b_2...a*b_1:1<=b_i<n\ and\ gcd(a,n)=1\}$
$反证：设存在i≠j;b_i,b_j∈S,有a*b_i=a*b_j(mod\ n)$
$由消去律得b_i=b_j(mod\ n)$
与条件矛盾，故得$S=S'$
所以

$$\prod_{i=1}^{φ(n)}b_i=\prod_{i=1}^{φ(n)}a*b_i=a^{φ(n)}\prod_{i=1}^φ(n)b_i(mod\ n)$$
由消去律得$a^{φ(n)}≡1\ (mod\ n)$

---

群

性质：

0.满足封闭性；
1.满足结合律；
2.存在单位元；
3.存在逆元。

单位元唯一性：

设$e'$亦为G的单位元
那么有：
$ee'=e'(e是单位元)$
$ee'=e(e'是单位元)$
所以$e=e'$

逆元唯一性：

设$g\in G,g的逆元为g^{-1},即gg^{-1}=e$
存在性：在群操作中，运算满足封闭性，h恒存在
唯一性：设有另一个逆元h,使得$gh=e$
那么：$gg^{-1}=gh$,由消去律得$h=g^{-1}$

子群(subgroup)：

$H中元素的集合是G的子集，H的群操作与G相同，称H是G的子群$

循环群(cyclic group)：

$g∈G,⟨g⟩={g^k:k∈Z}为循环群，g是生成元$

阶：

满足$g^n=e,取n的最小值,阶是n,记|g|=n$

例子：

群$Z_p^*$，阶为$φ(p)$,生成元个数$φ(φ(p))$,生成元$a$,有$gcd(a,φ(p))=1$
群$Z_{11}^*$,阶为$φ(p)=10$,生成元个数$φ(φ(p))=4$,生成元：$\{1,3,7,9\}$

定理1：

若存在正整数k，使得$g^k=e$ ,当且仅当k整除n.

证：
充分性：令$g^k=g^{ns}=e$
必要性：令$k=nq+r$
$e=g^k=g^{nq+r}=g^{nq}g^r=eg^r(0<=r<n)$
由消去律得：$g^r=0，故r=0$

定理2：

$h=g^k,h的阶为n/d,d=gcd(k,n)$

证：
设有正整数m,使得$h^m=g^{mk}=e$
$d=gcd(n,k)$
故$n\ |\ mk,那么：(n/d)\ |\ (k/d)m$
$由于(n/d)与(k/d)互素，无法整除$
故

$$(n/d)\ |\ (k/d)m=(n/d)\ |\ m$$
所以$m_{min}=n/d$

陪集(coset)

定义：

H是G的子群，对于$g∈G$
左陪集：$gH=\{gh:h∈H\}$
右陪集：$Hg=\{hg:h∈H\}$

例子:

设$H=\{[0],[2]\}是Z_4^+的subgroup，取所有g∈Z^+_4$
遍历:

$$[0]+H=\{[0],[2]\}① \\ [1]+H=\{[1],[3]\}② \\ [2]+H=\{[0],[2]\}③ \\ [3]+H=\{[1].[3]\}④$$
得①③，②④分别相等，所以左陪集有俩：$\{[0][2]\}$与$\{[1][3]\}$
同理可求右陪集

性质1：

H是G的subgroup，则有$g_1,g_2∈G,g_1H=g_2H或者g_1∩g_2=∅$

性质2：划分

所有左陪集构成一个划分，所有右陪集构成一个划分

拉格朗日定理

定义：

$G是有限群，H是G的子群，则|G|=|H|*[G:H]，[G:H]为H在G中右陪集的个数$

证：$设[G:H]=r;a_1,a_2...a_r分别为H的r个右陪集的代表元素$
由$G=Ha_1∪...Ha_r$
由于每个陪集不同，得：$|G|=|Ha_1|+...|Ha_r|\\|Ha_i|=|H|\\|G|=|H|*r=|H|[G:H]$

推论一：

群G的阶为n,所有$a∈G,|a|是n的因子，且有a^n=e$

推论二：

G是素数阶群,则存在$a∈G,G=<a>$

---

同构(Isomorphisms)

定义：

群$(G,·)\ and (H,*)$
满足one-to-one(单射) and onto(满射)映射
称φ为一个同构(isomorphic)

证明方法：

1.构造映射；
2.证明阶相同；
3.满足群操作；
4.双射
$\ (1)单射(one-to-one):利用反证法,a,b∈G,且a≠b,有f(a)≠f(b)$
$\ (2)满射(onto)：a∈G,b∈H，有f(a)=b恒成立$
5.群操作保持：
即先映射后计算等于先计算后映射(证同态)

同态(Homomorphisms)

定义：

群$(G,·)\ and (H,*)$，φ是两者间的一个映射，对于所有$a,b∈G$

$$φ(a·b)=φ(a)*φ(b)$$

正规子群(normal subgroup)

定义：

$H是G的子群，对于所有a∈G,有aH=Ha,称H为G的正规子群$(即左右陪集相等)

性质：

若$群G_1与G_2$同态，则
1.$e是G_1的单位元，那么，e也是G_2的单位元$
2.$对任何g∈G_1,φ(g^{-1})=[φ(g)]^{-1}$
3.$H_1是G_1的子群，那么，φ(H_1)是G_2的子群$
4.$H_2是G_2的子群，那么，φ^{-1}(H_2)是G_1的子群\\$
$H_2是G_2的正规子群，那么，φ^{-1}(H_2)是G_1的正规子群$

商群(quotient group)

定义：

$N是G的正规子群，对于所有a,b∈G,有(aN)(bN)=abN$
则$N的陪集{a,b}构成商群，记为G/N$

性质：

商群的阶等于陪集元素的个数
即$|G/N|=[G:N]$

例子：

$3Z^+是Z^+的正规子群$
得

$$0+3Z^+=\{...,0,3,6...\}\\ 1+3Z^+=\{...,1,4,7...\}\\ 2+3Z^+=\{...,2,5,8...\}$$
满足$(aN)(bN)=(abN)$

---

中国剩余定理

概念：

一种求一次同余式组的算法

算法：

有一次同余式组：

$$x≡a_1(mod\ m_1)\\ x≡a_2(mod\ m_2)\\ ......\\ x≡a_n(mod\ m_n)$$
解：
令：$M=\prod_{i=1}^nm_i$
$b_1=M/m_i$
$b'_i=b_i^{-1}(mod\ m_i)$(乘法逆元)
$$x=\sum_{i=1}^na_ib_ib'_i(mod\ M)$$

#algorithm of egcd
 def egcd(a,b):
    r0,r1,s0,s1=1,0,0,1
    while b:
        q,a,b=a//b,b,a%b
        r0,r1=r1,r0-q*r1
        s0,s1=s1,s0-q*s1
    return r0
#algorithm of CRT
def CRT(a,m):
    M,x=1,0
    b=list()
    b_=list()
    for n in range(len(m)):
        M=M*m[n];
    for i in range(len(m)):
        b.append(M//m[i])
        '''
        compute b_
        because b_[i]*b[i]=1(mod m[i])
        so b[i]*b_[i]-1=c1*m[i]
        than b[i]*b_[i]+c2*m[i]=1
        use egcd to compute the result
        '''
        b_.append(egcd(b[i],m[i]))
        '''
        when the result is a negative number
        let it become a positive number which is a Equivalence class about b_[i]
        '''
        if b_[i]<0:
            b_[i]=b_[i]%m[i]
        x=(a[i]*b[i]*b_[i]+x)%M
    return x

证明：

假设x0为解，且唯一。
由$b'_i(mod\ m_i)$的定义可知，恒有：

$$x_0\equiv a_i(mod\ m_i)(1\leq i\leq k)$$
而由于 $$x\equiv a_i(mod\ m_i)$$
得 $$x\equiv x_0(mod\ m_i)(1\leq i\leq k)$$
且由于$m_1,m_2...m_k$两两互素，故得 $$x\equiv x_0(mod\ m)$$
证毕。

例题：

Using CRT to solve the system of congruence:
x ≡ 1 (mod 5)
x ≡ 2 (mod 7)
x ≡ 3 (mod 9)
x ≡ 4 (mod 11)

解：由题得：
令：$m_1=5,m_2=7,m_3=9,m_4=11;$
所以

$$M=\prod_{i=1}^4m_i=3465$$
$a_1=1,\ a_2=2,\ a_3=3,\ a_4=4;$
$b_i=M/m_i;\ b_i^{'}=b_i^{-1}(mod\ m_i)$
$b_1=693,\ b_2=495,\ b_3=385,\ b_4=315;$
因为$b_ib_i^{-1}=1(mod\ m_i)$
得$b_ib_i^{-1}-1=c_cm_i$
$b_ib_i^{-1}+c_2m_i=1$
由拓展欧几里得算法解得
$b_1^{'}=2,\ b_2^{'}=3,\ b_3^{'}=4,\ b_4^{'}=8$
$$x=\sum_{i=1}^4a_ib_ib_i^{'}(mod\ M)$$
解得$x=1731$

---

大整数分解

pollard's p-1算法

目的：

求合数N的数因子

思路及算法：

1.设数字m,且$(p-1)|m$,p是素数且为N的因子
那么，由费马小定理得：
$a^m≡1(mod\ p)$
故有$p|gcd(a^m-1,N)$;
2.令$m=n!(2<n<N)$;
3.计算$gcd((a^{n!}mod\ N)-1,N)$;
4.若结果为1或者N,n自增1，重复步骤2-3，否则，$p=gcd((a^{n!}mod\ N)-1,N)$,即为答案;

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def Pollard_PM1(N):
    a=2
    for i in range(2,N):
        a=(a^i)%N
        divisor=gcd(a-1,N)
        if divisor!=1 and divisor!=N:
            return divisor
    return 1

pollard's rho算法

目的：

求合数N的数因子

思路及算法

1.假设N有两个数因子x和y
令$x≡y(mod\ N)$
2.设有函数$F()$
令$x=F(x),y=F(F(x))$
$d=gcd(x-y,N)$,$当d!=1\ and\ d!=N时$，d即为答案

#伪代码
def PollardRho(N):
    x1 = x2 = Random_ZN_Star(N)
    for i in range(1, 2^(N.nbits()//2)):
        x1 = F(x1, N)
        x2 = F(F(x2, N), N)
        p = gcd(x1 − x2, N)
    if p != 1 and p != N:
        return p

设$F(x)=x^2-1$

import random
import cmath
def F(x):
    return x^2-1
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def PollardRho(N):
    i,k=1,2
    x=random.randint(0,N-1)
    y=x
    while True:
        i=i+1
        x=F(x)%N
        divisor=gcd(y-x,N)
        if divisor!=1 and divisor !=N:
            return divisor
        if i==k:
            y,k=x,2*k

---

离散对数

g是群G的生成元，|G|=p-1,$g^x=y$,求y

Pohlig-Hellman 算法

1.令

$$p-1=\prod_{i=1}^tp^{k_i}_i=p^{k_1}_1p^{k_2}_2...p^{k_t}_t$$
2.$g_i=g^{x_i}=g^{(p-1)/{p_i^{k_i}}}$
得$x_i=(p-1)/p_i^{k_i}与p_i^{k_i}互素$
那么：$y_i=y^{(p-1)/p_i^{k_i}}$有$g^{x_i}=y_i$
由于$g^{{x_i}{p_ik_i}}=e,即g^{x_i}的阶为p_i^{k_i}且其与x_i互素$
故得$x=x_i(mod\ p_i^{k_i})$

思路：

为求x，构造一组一次同余式组，以CRT求解。
那么，每个$x_i$可以用p-1的各个因子去构造。

#Problem: Given base g, y \in <g>, y = g^x mod p, to find x.
def Pohlig_Hellman(y, g, p):
    prime_list = factor(p − 1)
    n = len(prime_list)
    q_list = [prime_list[i][0]^prime_list[i][1] for i in range(n)]
    G = [ g^((p − 1) // q_list[i]) for i in range(n) ]
    Y = [ y^((p − 1) // q_list[i]) for i in range(n) ]
    val_list = [discrete_log(Y[i], G[i]) for i in range(n)]
    modulus_list = [q_list[i] for i in range(n)]
    x = crt(val_list, modulus_list) # solve the CRT problem.
    return x

大步小步算法

1.大步

令$s=\lfloor\sqrt{p}\rfloor$
那么有$g^0,g^s,g^{2s}...g^{\lfloor p/s \rfloor s}$

2.小步

令$y为其中某一元素$
有$y*g,y*g^2...y*g^s$

3.算x

得$y*g^r=g^xg^r=g^{st}$
故$x=st-r(mod\ p)$

# Input: g,y,n where g is the base, y = g^x mod p,
def BGS(g, y, p):
    s = floor(sqrt(p))
    A = [(y*(g^r) % p) for r in range(0, s)] #Baby Step.
    B = [(g^(t*s) % p) for t in range(1, s+1)] #Giant Step.
    r,t = 0,0
    for u in A:
        for v in B:
            if u == v: #Collision.
                r, t = A.index(u), B.index(v)
    return ((t+1)*s − r) % p # Return x

pollard's rho算法

算法

1.设置变量：
$lefta=g^{lg}y^{ly};right=g^{rg}y^{ry};$
2.设置随机函数F()
令$lefta=F(lefta);righta=F(righta)以此迭代$
直到出现$lefta=righta$
3.那么

$$g^{lg}y^{ly}=g^{rg}y^{ry}\\ g^{lg}g^{xly}=g^{rg}g^{xry}\\ lg+xly=rg+xry\\ x=(rg-lg)/(ly-ry)$$

#Input: y = g^x mod p; Output: x
def PollardRhoDLOG(y):
    lefta, lg, ly = 1, 0, 0 # lefta = g^lg * y^ly
    righta, rg, ry = y, 0, 1 # righta = g^rg * y^ry
    while lefta != righta:
        lefta, lg, ly = F(lefta, lg, ly)
        righta, rg, ry = F(righta, rg, ry)
        righta, rg, ry = F(righta, rg, ry)
    s, t = lg − rg, ry − ly
    if s == 0:
        return ’fail’
    return s * (t^(−1))

关于随机函数

Pollard suggests：

$$F(x)= \begin{cases} ga& \text {0<=a<q/3}\\[2ex] a^2 & \text q/3<=a<2q/3\\[2ex] ya & \text 2q/3<=a<q\\ \end{cases}$$

时间开销

Θ(√q)