2018年数论课鄙记

根据SCNU斌头老师的课件整理
整理者：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$

时间复杂度：

$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} r_0 & s_0 & a\\ r_1 & s_1 & b\\ \end{bmatrix} = \begin{bmatrix} r_1 & s_1 & b\\ r_0-q*r_1 & s_0-q*s_1 & a\%b\\ \end{bmatrix} =... = \begin{bmatrix} r_{n} & s_{n} & a\%..\%b\\ r_{n-1}-q*r_{n} & s_{n-1}-q*s_{n} & 1\\ \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)$

米勒拉宾素数测试

米勒拉宾算法：

一种检测一个整数是否为素数的算法，准确率约大于3/4，即伪素数通过检验的概率约小于1/4。
介绍该算法前，先了解素数的两个性质。

若 $p$ 是素数，那么存在 $1<a<p$ ，当且仅当 $a\ mod\ p=1$ 或 $a\ mod\ p=-1=p-1(\mbox{逆元})$ 时，有 $a^2\ mod\ p=1$
若 $p$ 是素数，且 $p>2$ 那么有： $p-1=2^kq,k>0,2 \nmid q$ ,有 $a\in (1,p-1)$ ,满足一下条件之一：
(1). $a^q\equiv 1(mod\ p)$
(2). 在 $a^q,a^{2q},a^{4q}...a^{2^{(k-1)}q}$ 中，必然存在一个数模p与-1同余

理解这两个性质：
首先，从费马小定理出发，有 $a^{(p-1)}\equiv 1(mod\ p)$ ,那么，由于p是素数，所以 $2\ |\ p-1$ ,那么 $p-1$ 可表示为 $p-1=\displaystyle\frac{p-1}{2}*2$
那么得 $a^{(p-1)}=a^{\frac{p-1}{2}*2} \equiv 1(mod\ p)$ ,那么必然有 $a\ mod\ p=1$ 或 $a\ mod\ p=-1=p-1(\mbox{逆元})$ (由此理解性质1)
然后，将 $(p-1)$ 按以上思路进行分治，直到 $(p-1)=2^kq,2 \nmid q$ ,分治过程中，要么所有值都为1，那么必然 $a^q\equiv 1$ ;或者中间某个值为-1.(由此理解性质2)

算法步骤：

将 $(p-1)$ 分解至 $(p-1)=2^kq,2 \nmid q$ ,得到q
选取随机数 $a,a \in (1,p-1)$
若 $a^q\ mod p=1$ ,通过检验;否则循环一下操作
计算 $a^{2^jq}$ ,其中 $j\in(0,k-1)$ 若出现有结果为-1,那么通过检验，否则不通过

应用：

一般用作检验时，循环10次以上米勒拉宾操作，以保证正确概率。
可用该算法，随机生成一个大整数，然后检验该数是否为素数的方法，生成随机素数。

代码：

#A quickly multiply algorithm with modding n
def Qmul(a,b,n):
    r=0
    while b:
        if b&1:
            r=(r+a)%n
        b=b>>1
        a=(a<<1)%n
    return r

#A quidckly exponential algorithm with modding n
def QPow(a,x,n):
    result=1
    while x:
        if x&1:
            result=(result*a)%n
        x=x>>1
        a=(a*a)%n
    return result

#Find the number = (n-1)/2^k
def Find_q(n):
    while not n&1:
        n=n>>1
    return n

#Miller Rabin algorithm
def Miller_Rabin(a,n):
    q=Find_q(n-1)
    aq=QPow(a,q,n)
    #final condition,q=n-1
    while q<n:
        if aq==1 or aq==-1:
            return True
        #make aq = aq(q*2^j)
        aq=QPow(aq,2,n)
        q=q<<1
    return False

群

性质：

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

证明：

思路：构造法证存在；反证法证唯一。

例题：

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$ ,求 $x$

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}$

时间开销

Θ( $\sqrt q$ )