筑基篇·初等数论

密码学学习笔记——筑基篇·卷一（初等数论）

---

说在前面

在学习、比赛的过程中，感觉没有数竞基础的同学入坑Crypto真的很痛苦，很多概念和符号都不懂。

所以在此分享自己的数学基础学习笔记(九年制义务教育都能看得懂的那种，建议加入中考😀),因为都是基础知识，就命名为《筑基篇》吧，希望能减轻大家入坑密码的痛感，大家一起快乐的学习吧！！！

当然，看我这篇笔记肯定是不够的，有些证明过程我也是直接省略了，大家还是要把密码学涉及到的全部知识系统的学习一遍，很重要的一点是学会动笔！。

如果以后我润别的方向了，也算给自己的CTF的Crypto生涯一份结果。

如果有错误也恳请大家指正，爱来自NJUST。

那么，筑基篇，正式开始!!!!!

PS1：由于各人编辑器的使用习惯差异，符号字母也是markdown公式编辑手搓出来的，发布出来的公式渲染可能会出一点点小问题，大家多包涵，对于渲染不出来的公式，大家可以自己复制到typora里看😀。

PS2：编辑器和我个人水平差的缘故，可能排版、内容顺序杂乱，大家轻点喷

PS3：有修改建议的话可以发邮件捏email: Cucumber0703@outlook.com ,看到后会光速滑轨修改的

---

初等数论

---

整除性（Divisibility）

$$\begin{flalign*} b|a:&设a,b∈\mathbb{Z}，如果存在一个q∈\mathbb{Z}\\& 使得a=qb，则称“b整除a”，记为“\ b|a\ "\\& (或称：b是a的因子，a是b的倍数，a被b整除)\\& & \end{flalign*}\\$$ $$\begin{flalign*} b\nmid a：&b不能整除a(a不能被b整除\\& b|a \iff a=qb\\& & \end{flalign*}\\$$ $$\begin{flalign*} &对于任意a,b,c∈\mathbb{Z}，有：\\& (1)b|0\\& (2)1|a\\& (3)0|a\iff a=0 (部分教材说明b可为0，由于在定义中为乘法关系a=qb，故虽然a被b整除，b依旧可为0)\\& (4)b|a\iff b|-a \iff -b|a\\& (5)b|a且a|b当且仅当a=±b，特别地，a|1当且仅当a=±1\\& & \end{flalign*}\\$$

• (自反性) $a|a$
• (传递性) $b|a且a|c,则b|c$
• (相乘性) $b|a，则bc|ac$
• (消去性) $bc|ac且c≠0，则b|a$
• (线性性) $b|a且b|c，对于所有s,t∈\mathbb{Z},都有b|(sa±tc)$
• (比较性) $如果a,b∈\mathbb{N}且b|a，则b≤a$

练习题1：

证明对于任何自然数，让其各位上的数字相加之和如果能被3整除，那么这个自然数也可以被3整除

---

素数（Prime）

• 定义：$设n∈\mathbb{N}且n≥2，除了1和n以外，没有其他正整数整除n，n称作“素数”(通常用p表示)；否则，n称作“合数”$

  PS：$1既不是素数也不是合数$

  PS：$n为合数，则n=ab，其中1<a<n，1<b<n$

引理：任何大于1的整数必有素因子。

定理：任何合数n都至少有一个不超过$\sqrt{n}$的素因子（n>1是合数，则存在素数p，使p≤$\sqrt{n}$）

• 判断n是否是素数，如果所有素数p≤$\sqrt{n}$都不能整除n，则n是素数

定理：算数基本定理：任何非零整数n，可以表示成如下的乘积形式：

$$n=\pm p_1^{e_1}\dots p_r^{e_r}$$

​ 其中，$p_1,\dots ,p_r是互不相同的素数，e_1,\dots，e_r是正整数$。

• PS：这个表示形式唯一（忽略顺序），认为$\pm1$可以表示成0个素因子项相乘（r=0），通常把0个素数相乘的结果作为1。

定理：$设p是素数，a,b∈\mathbb{Z},则p\mid ab \Rightarrow p\mid a或p\mid b$

推论：$设p是a_1,\dots ,a_k\in \mathbb{Z},则p\in a_1\dots a_k \Rightarrow p \in a_i,i \in \{1,\dots,k\}$

定理：欧几里得定理：素数有无穷或多个

​ 证明略

---

模运算

$$a\ mod\ b：设a，b∈ \mathbb{Z}且b>0,如果q,r∈\mathbb{Z}满足\\a=qb+r,且0\leq r<b,\\则定义：a\ mod\ b=r$$

负数怎么求模？

用b不断加a，直至大于0

性质：

• $b|a \iff a\ mod\ b=0$
• $(a+b)\ mod\ n=(a\ mod\ n+b\ mod n)\ mod\ n$
• $(a-b)\ mod\ n=(a\ mod\ n-b\ mod n)\ mod\ n$
• $(a\times b)\ mod\ n=(a\ mod\ n\times b\ mod n)\ mod\ n$

乘法逆元（一定要说明是在哪个模数下的乘法逆元）

九年制义务教育中的概念：倒数：两个数的乘积为1，就称这两个数互为倒数

定义：$设a\in \mathbb{Z},n\in \mathbb{N},如果 az \equiv1 \pmod n,$
$称z是模n下a的乘法逆元，记作a^{-1}=z。$

例：

$2^{-1}\ mod\ 7=4$

$2^{-1}\ mod\ 5=3$

• 注意1：$模n下互为乘法逆元，一般只考虑比n小的$

• 注意2：$a在模n内的乘法逆元a^{-1}(1\le a^{-1} \lt n)是唯一的$

• 注意3：乘法逆元存在的条件：

  $gcd(a,n)=1\iff 模n下，a有乘法逆元$

怎么求乘法逆元，见下面——扩展的欧几里得算法

---

最大公约数

• $设a,b∈\mathbb{Z},如果d∈\mathbb{Z}且d|a，d|b，则称d是a和b的公因子(公约数)$
• $如果d≥0，且a和b的所有公因子都整除d，则称d是a和b的最大公约数，记作gcd(a,b).$

PS:公因子可以是任意整数（包括0，负整数）

PS:最大公约数只能是0或正整数，不能是负的

欧几里得算法 (辗转相除法)

不失一般性，设a≥b≥0，求gcd(a,b)

数学原理：

$b=0时，gcd(a,0)=a$（任何整数都是0的公因子）

$$b>0时，gcd(a,b)=gcd(b,r)=gcd(r,r_1)\\=gcd(r_n,0)=r_n$$

PS：r为余数，a=qb+r

扩展的欧几里得算法(广义欧几里得算法)

用途：$计算as+bt=gcd(a,b)中的s和t$

本质是在执行欧几里得算法的时候利用每一步计算出来的余数以及副产品“商”，顺道迭代的计算出每一步对应的s和t

裴蜀定理

$若a,b是整数,且 gcd (a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立$

注意：此处的x和y是整数（即可以是负数）

定理：最大公约数表示定理

$设a,b∈\mathbb{Z},d=gcd(a,b),则\exists s,t∈\mathbb{Z},使得as+bt=d$

特别地：$gcd(a,b)=1\iff as+bt=1$

推论：$d\mid v\iff as+bt=v$

求乘法逆元

$设gcd(a,n)=1$

$根据最大公约数表示定理，有$

$as+tn=1$

$等式两边同时模n，得$

$as\equiv1\pmod n$

$易知，模n下a的逆元是s$

---

互素

• $设a,b∈\mathbb{Z},如果gcd(a,b)=1,则称a和b互素。$

• $设gcd(a,b)=d,则存在q_1,q_2\in \mathbb{Z},使得a=q_1 d,b=q_2d,且gcd(q_1,q_2)=1$

---

最小公倍数(LCM)

• $设a,b∈\mathbb{Z},如果m∈\mathbb{Z}分别是a和b的倍数，m称作a和b的公倍数$

  $如果a\mid c,b\mid c,则m\mid c$

• $lcm(a,b):a和b的最小公倍数$

• $a,b≠0：m是a和b所有正的公倍数中最小，m叫作a和b的最小公倍数$
• $a=0或b=0：lcm(a,b)=0$

• $gad(a,b)=1\Rightarrow lcm(a,b)=ab$

• $lcm(a,b)=ab/gcd(a,b)$

  求lcm：两个数不断加自己，直至相等。

---

等价关系

同时满足自反性，对称性，传递性

例：>只满足传递性，≥不满足对称

同余关系

$a\equiv b \pmod n$：设n为正整数(此处被称为模数)，整数a和b分别模n，如果得到相同的余数，就称a和b在模n下满足同余关系，简称同余（此处为关系，而非运算，与$a\ mod \ b$进行区分）

定义：$设a,b,n∈\mathbb{Z},n\mid (a-b),就称a和b在模n下同余，记作a\equiv b\pmod n。$

是一种等价关系

运算性质：加减乘(甚至是和乘方)仍然满足同余关系，除法有需要特别注意的地方。

一次同余方程

$x\equiv b \pmod n的解集：{b\pm nk,其中k=0,1,2,3\dots}$

• 一个规律：$原模数为n,最终模数为n^{’},设n/n{’}=d，有0\sim n-1之间解的数量恰好等于d$

• 有解的条件：$若gcd(a,n)=d,则ax\equiv b\pmod n有解\iff d\mid b$

消去律

$定义：设a,n\in \mathbb{Z},n>0,如果gcd(a,n)=d,有$

$az\equiv az^{‘}\pmod n\ \Rightarrow \ z\equiv z^{‘}\pmod {n/d}$

---

剩余类(一种等价类)

等价类的概念

$设\sim是集合S上的等价关系，对于a\in \mathbb{S},定义其等价类为\{x\in \mathbb{S}\ |\ x\sim a\}$

• $\mathbb{S}中每个元素必存在于唯一的等价类中$
• $所有等价类的并集恰好就是\mathbb{S}$

剩余类(满足等价类所有性质)

$设a\in \mathbb{Z}，定义其剩余类为\{x\in \mathbb{Z}\ |\ x\equiv a\pmod n \ \}$

$模n下含整数a的剩余类，记作[a]_n,不引起歧义时，简记为[a]$

$剩余类里的每个整数都叫作这个剩余类的代表元，比如模5下,-10,-5,0,5,10都是[0]的代表元$

剩余类集：$\mathbb{Z_n}$

$\mathbb{Z_n}=\{[0],[1],[2]\dots\,[n-1]\}$

$\mathbb{Z_5}=\{[0],[1],[2],[3],[4],\}$

运算

$[a]+[b]:=[a+b]$

$[a]·[b]:=[a·b]$

$其中a,b\in \mathbb{Z}$

$设u,v\in \mathbb{Z_n},若uv=[1],则u和v互为乘法逆元$

$设u=[a],v=[b],则$

​ $u和v互为乘法逆元\iff ab \equiv1 \pmod n$

​ $即u(和v)有乘法逆元\iff a(和b)与n互素$

$\mathbb{Z^{*}_n}=\{\mathbb{Z_n}中有乘法逆元的剩余类\}$

​ $=\{[a]\ |\ a=0,1,\dots,n-1,gcd(a,n)=1\}$

• $n为素数：\mathbb{Z^{*}_n}=\mathbb{Z_n} \setminus \{[0]\}$

• $n为合数：\mathbb{Z^{*}_n} \subsetneq \mathbb{Z_n}\setminus\{[0]\}$

不引起起义的情况下，[ ]可以省略

---

中国剩余定理(孙子定理)

$设两两互素的模数n_1,\dots,n_m\in \mathbb{N},以及任意整数a_1,\dots,a_m\in \mathbb{Z},并设n={\prod}\limits_{i=1}^mn_i,方程组$

​ $\left \{ \begin{array}{c} x\equiv a_1\pmod {n_1} \\ \dots \\ x\equiv a_m\pmod {n_m} \end{array} \right.$

$必有解，设解为a\in \mathbb{Z}。并且对任意a^{’}\in \mathbb{Z},都有$

$a^{’}是方程组的解\iff a\equiv a^{‘}\pmod n$

$设n=\prod_{i=1}^mn_i$

$$n_1^{*}=n/n_1,\dots,n_i^{*}=n/n_i,\dots,n_m^{*}=n/n_m$$

​ $gcd(n_1^{*},n_1)=1,\dots,gcd(n_i^{*},n_i)=1,\dots,gcd(n_m^{*}，n_m)=1$

​ $t_1n_1^{*}\equiv1 \pmod {n_1},\dots,t_in_i^{*}\equiv1 \pmod {n_i},\dots,t_m n_m^{*}\equiv 1 \pmod {n_m}$

​ $e_i=t_in_i^{*}\equiv\left \{\begin{array}{c}1\pmod {n_i} \\\ 0\pmod {n_j},j\neq i \end{array} \right.$

​ $a={\sum}\limits_{i=1}^{m}e_ia_i=e_1a_1+\dots+e_ma_m$

$$a={\sum}\limits_{i=1}^{m}n_i^{*}n_i^{-1}a_i$$

例：三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

自己去搜索《孙子歌诀》，看看老祖宗的智慧

笔者在此一遍此处的做法

$$\left \{ \begin{array}{c} x\equiv 2\pmod{3} \\ x\equiv 3\pmod {5}\\ x\equiv 2\pmod {7} \end{array} \right.$$

$n=3\times 5\times7=105$

$$n_1^{*}=n/n_1=35,n_2^{*}=n/n_2=21,n_3^{*}=n/n_3=15$$ $$n_1^{*-1}=2，n_2^{*-1}=1，n_3^{*-1}=1，$$ $$PS:n_i^{*-1}为n_1^{*}模n_i的乘法逆元$$ $$e_1=35*2=70,e_2=21*1=21,e_3=15*1=15$$ $$a={\sum}\limits_{i=1}^{m}n_i^{*}n_i^{-1}a_i=233$$

$最后，105内的唯一解即为233\ mod\ 105=23$

中国剩余映射

$设两两互素的模数n_1,\dots,n_m\in \mathbb{N},n={\prod}\limits_{i=1}^mn_i,则中国剩余映射$

$\tau：\mathbb{Z_n}\rightarrow \mathbb{Z_{n_1}}\times\dots\times \mathbb{Z_{n_m}}$

​ $a\rightarrow(a\ mod\ n_1,\dots,a\ mod\ n_m)$

$是一个双射$

• $将所有\mathbb{Z}换成带*的，式子依然成立$

---

欧拉函数

孩子们，看到这里，不妨先往前翻几章，看看剩余类中提到的一个概念

$\mathbb{Z^{*}_n}=\{\mathbb{Z_n}中有乘法逆元的剩余类\}$

​ $=\{[a]\ |\ a=0,1,\dots,n-1,gcd(a,n)=1\}$

• $n为素数：\mathbb{Z^{*}_n}=\mathbb{Z_n}\setminus\{[0]\}$

• $n为合数：\mathbb{Z^{*}_n}\subsetneq \mathbb{Z_n}\setminus\{[0]\}$

不引起歧义的情况下，[ ]可以省略

定义：

$对于所有正整数n\in \mathbb{N},定义欧拉函数$

$\phi(n)=|\mathbb{Z_n^{*}}|$

$且令\phi(1)=1$

$或者说,0 \sim {n-1}之间与n互素的整数有多少个，\phi(n)就等于几$

三个性质

• $性质一：设两两互素的正整数n_1,\dots,n_m\in \mathbb{N},并设n={\prod}\limits_{i=1}^mn_i,$

  $\phi(n)={\prod}\limits_{i=1}^m\phi({n_i})$

• $性质2：\phi(p^k)=p^{k-1}\phi(p)$

• $性质3：\phi(p)=p-1$

例子:

$$\begin{flalign*} &\phi(30000)\\& =\phi(3*2^4*5^4)\\& =\phi(3)*\phi(2^4)*\phi(5^4)\\& =\phi(3)*2^3\phi(2)*5^3\phi(5^4)\\& =2*2^3*1*5^3*4\\& =8000\\& & \end{flalign*}\\$$

---

乘法阶(Multiplicative Order)

$设a\in \mathbb{Z_n^{*}},使得a^k\equiv1\pmod n的最小正整数k称作a在模n下的乘法阶。用ord_n(a)表示。$

$$设a\in \mathbb{Z_n^{*}}的(乘法)阶为k，则以下整数能彼此不同\\a^0,a^1,a^2,\dots,a^{k-1}\\所有运算都模n$$ $$a^i\equiv a^j\pmod n,其中i>j\\a^i/a^j\equiv a^j/a^j\pmod n\\a^{i-j}\equiv1\pmod n\\a^t\equiv1\pmod n,令t=i-j$$

性质：

• $a^i\equiv1\pmod n\iff k\mid i$
• $a^i\equiv a^j\pmod n\iff i\equiv j \pmod k$

例：设a在模7下的阶为3，则

$a^{101}\equiv a^{101\ mod\ 3}\equiv a^2(mod\ 7)$

性质1:$\forall m\in \mathbb{Z},有ord_n(a)|m\Leftrightarrow a^m\equiv1\pmod n$

性质2:$a,a^2,a^3,\dots,a^{ord_n(a)}=1各不相同$

性质3:$\forall k\in \mathbb{Z},则a^k的乘法阶为ord_n(a)/gcd(k,ord_n(a))$

性质4:$ord_n(a)|\phi(n)$，$ord_p(a)|(p-1)$

性质5：$d$是$\phi(n)$的正因子，$Z_n^*$里的$d$阶元素一共有$\phi(d)$个

---

欧拉定理(Euler’s theorem)&费马小定理(Fermat’s little theorem)

欧拉定理：$设a\in \mathbb{Z_n^{*}},则\\a^{\phi(n)}\equiv1\pmod n$

$且k\mid \phi(n),其中k是a在模n下的阶$

$a^{\phi(p)}\equiv 1\pmod p$

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

两边都乘a

得到$a^p\equiv a\pmod p$

即费马小定理$(对于任意素数p和整数a\in \mathbb{Z_p},都有a^p\equiv a\pmod p)$

例题：

求$3^{2022}\ mod\ 8$

$gcd(3,8)=1,可用欧拉定理$

$\phi(8)=\phi(2^3)=2^2\phi(2)=4,所以3^4\equiv1\pmod 8$

$$3^{2022}\ mod\ 8\\=3^{505\times4+2}\ mod\ 8\\=3^2\ mod\ 8\\=1$$

定理：$设a\in \mathbb{Z_n^{*}},m\in \mathbb{Z},a在模n下的乘法阶为k，则a^m在模n下的乘法阶为k/gcd(m,k)$

$证明:设a^m的阶为t,则 (a^m)t\equiv1\mathrm{~(mod~n)}$
$所以 a^{mt}\equiv 1\pmod n,必有 k|mt $
$则有 mt \equiv 0\pmod k$
$t\equiv 0\pmod{k/gcd(m,k)}$

例题：

$设a\in Z_n^{*}的乘法阶是6，求a^9的乘法阶$

$$解：k=6，m=9，\\gcd(k,m)=3,则\\阶为k/gcd(k,m)=2$$

---

二次剩余(Quadratic residue)

$x^2\equiv a\pmod {n}$

$$定义：设a\in \mathbb{Z}_n^{*},如果存在整数b\in \mathbb{Z},\\使得b^2\equiv a\pmod n,\\则称a为模n下的二次剩余，\\并称b为a在模n下的平方根$$

二次剩余的集合：$(\mathbb{Z}_n^{*})^2$

$$(\mathbb{Z}_n^{*})^2=\{b^2|b\in \mathbb{Z_n^{*}}\}$$ $$a,b\in \mathbb{Z_n}或\mathbb{Z_n^{*}}时，ab\ mod\ n,简写为 ab$$ $$若a\in \mathbb{(Z_n^{*}})^2,则存在b\in \mathbb{Z_n^{*}}，使得b^2\equiv a\pmod n)$$

$a是模n下的二次剩余\iff a\in (\mathbb{Z_n^*})^2$

模p下的二次剩余

• $设p是奇素数(p是素数，且p\neq2)$

  $1.设b\in \mathbb{Z_p},则b^2=1\iff b=\pm1$

  $2.设b,c\in \mathbb{Z_p^*},则b^2=c^2\iff b=\pm c$

  $3.|(\mathbb{Z_p^*})^2|=(p-1)/2$

欧拉准则(Euler’s criterion)

$设p是奇素数，a\in \mathbb{Z_p^*,}则$

• $1.\ a^{\frac{p-1}2}=\pm1$(证明依据欧拉定理)

• $2.\ a\in (\mathbb{Z_p^*})^2\Rightarrow a^{\frac{p-1}2}=1$

• $3.\ a\notin (\mathbb{Z_p^*})^2\Rightarrow a^{\frac{p-1}2}=-1$

  $设p是奇素数，a,b\in \mathbb{Z_p^*},则a,b同为二次剩余或二次非剩余时，ab为二次剩余\(ab)^{\frac{p-1}2}=a^{\frac{p-1}2}b^{\frac{p-1}2}$

模p下$-1$的平方根

• $性质一：p\equiv 1\pmod 4\iff {-1}\in(\mathbb{Z_p^*})^2$
• $$性质二：设p\equiv 1\pmod 4,c\in \mathbb{Z_p^*}\setminus(\mathbb{Z_p^*})^2\\令b:=c^{\frac{p-1}4}\pmod p,则\\b^2\equiv -1\pmod p$$

费马二平方定理（Fermats’s two squares theorem）

$$设p是奇素数，则\\p\equiv 1\pmod 4\iff p=s^2+t^2,s,t\in \mathbb{Z}$$

求平方根

$p\equiv 3\pmod 4求二次剩余的平方根$

$设a\in (\mathbb{Z_p^*})^2，p\equiv 3\pmod 4，则a的一个平方根为b=a^{\frac{p+1}{4}}$

通用算法(Tonelli-Shanks算法)(a是二次剩余，求a的平方根)

$p是奇数\Rightarrow p-1是偶数\Rightarrow p-1=2^tm(m是奇数，令m=2q+1)$

1.$计算t、m,满足p-=2^tm$

2.$找一个u\in Z_p^*\setminus (Z_p^*)^2,计算a^m和u^m$

3.$计算x，使得(u^m)^x=a^m$

4.$计算k=u^{\frac{mx}2}(易知，k^2=a^m)$

5.$output：\pm ka^{-q}$

$(\pm ka^{-q})^2=k^2a^{-2q}=a^ma^{-2q}=a^{m-2p}=a$

PS:$t=1时，p=2m+1=2(2q+1)+1=4q+3\Rightarrow p\equiv 3\pmod 4$

​ $t>1时，不断地随机寻找整数u，直到(\frac{u}p)=-1为止$

模$p^k$下的二次剩余

$p是奇素数，k是正整数,p^k\mid a\Rightarrow p\mid a$

$1.设b\in \mathbb{Z_{p^k}},则b^2=1\iff b=\pm1$

$2.设b,c\in \mathbb{Z_{p^k}^*},则b^2=c^2\iff b=\pm c$

$3.|(\mathbb{Z_{p^k}^*)}^2|=\phi(p^k)/2$

$设p是奇素数，a\in \mathbb{Z_{p^k}^*},则$

• $1.\ a^{\frac{\phi(p^k)}2}=\pm1$(证明依据欧拉定理)

• $2.\ a\in (\mathbb{Z_{p^k}^*)}^2\Rightarrow a^{\frac{\phi(p^k)}2}=1$

• $3.\ a\notin (\mathbb{Z_{p^k}^*)}^2\Rightarrow a^{\frac{\phi(p^k)}2}=-1$

  $$设p是奇素数，a,b\in \mathbb{Z_p^*},则a,b同为二次剩余或二次非剩余时，ab为二次剩余\\(ab)^{\frac{p-1}2}=a^{\frac{p-1}2}b^{\frac{p-1}2}$$

$$a\in (\mathbb{Z_{p^k}^*})^2\iff a\in (\mathbb{Z_p^*})^2$$

求平方根

$gcd(a,p)=1,k>1是整数$

$a是模p^k下的二次剩余\iff a是模p下的二次剩余\ \ \underrightarrow{Tonelli-Shanks算法}\ \ 模p下的平方根\\ \rightarrow 模p^2下的平方根\rightarrow\dots\rightarrow 模p^k下的平方根(Hensel\ lifting)$

Hensel lifting技术

$设t\geq 1是整数，a在模p^t下的平方根是b，即b^2\equiv a\pmod {p^t}$

$目标：利用b，求出a在模p^{t+1}下的平方根c$

$c^2\equiv a\pmod {p^{t+1}}\Rightarrow c^2\equiv a\pmod {p^t}\Rightarrow c^2\equiv b^2\pmod{p^t}\Rightarrow c\equiv \pm b\pmod{p^t}$

$设c=b+p^tv,则有c^2\equiv (b+p^tv)^2\equiv b^2+2bp^tv\pmod {p^{t+1}}(完全平方展开)$

$a-b^2\equiv 2bp^tv\pmod{p^{t+1}}$

$\frac{a-b^2}{p^t}\equiv 2bv\pmod p\Rightarrow v\equiv (\frac{a-b^2}{p^t})(2b)^{-1}\pmod p$

模n下的二次剩余

$设n>1是奇数，且n=p_1^{k1}\times\dots\times p_m^{k_m}$

• $a\in (Z_n^*)^2\iff a_i\in(Z_{p_i^{k_i}})^2,i=1,\dots,m$

• $|(Z_n^*)|=\phi(n)/2^m$

• $a\in (Z_n^*)^2,则a恰好有2^m个平方根$

  $$a\in (Z_n^*)^2\iff a\pmod {p_i^{k_i}}\in (\mathbb{Z_{p_i^{k_i}}^*})^2\iff a\pmod {p_i} \in (\mathbb{Z_{p_i}^*})^2,i=1,\dots,m$$

例：$45=3^2×5 ，此时m = 2$

所以： $|\mathbb{(Z_{45}^∗)^2}|=\frac{\phi(45)}{2^2}=6 。$

可以用中国剩余映射计算： $(\mathbb{Z_9^∗})^2={1,4,7} , (\mathbb{Z_5^∗})2={1,4}$

可得：

$(\mathbb{Z_9^∗})^2×(\mathbb{Z_5^∗})^2={(1,1),(1,4),(4,1),(4,4),(7,1),(7,4)}$

然后用中国剩余定理就可以求解具体二次剩余。

平方根找法：比如$(1，4)$可以拆解为

$(Z_9^∗)×(Z_5^∗)={(1,2),(−1,2),(1,−2),(−1,−2)}$

求平方根

$n=p_1^{k_1}\dots p_m^{k_m}是奇合数$

$a(=b^2)\ \underrightarrow{中国剩余映射}\ (a_1,\dots,a_m)\rightarrow (b_1,\dots,b_m)\ \underrightarrow{中国剩余定理}\ b$

若已知“求平方根“的高效算法，可构造高效算法来“因子分解n”

原理：$n=pq$确定性算法A(a,n)返回a在模数n下的一个平方根

B(n):$随机选择b\in \{1,\dots,n-1\}$

​ $if\ d:=gcd(b,n)>1:output\ \ d,n/d$

​ $else\ a=b^2,b’=A(a,n)$

​ $if\ b’=\pm b: output\ ‘failure’$

​ $else\ output\ d’:=gcd(b-b’,n),n/d’$

$n的平方根$	模p、q后余数形成的二元组
b	$(b_1,b_2)$
-b	$(-b_1,-b_2)$
b’	$(-b_1,b_2)$
-b’	$(b_1,-b_2)$

$b-b’\rightarrow(b_1,b_2)-(-b_1,b_2)=(2b_1,0)\rightarrow\ 模q为0，是q的倍数$

归纳

	二次剩余数量	二次剩余的平方根
$p$	$\phi(p)/2(集合大小的一半）$	$2个$
$p^k$	$\phi(p^k)/2(集合大小的一半）$	$2个$
$n$	$\phi(n)/2^m(集合大小的1/2^m)$	$2^m个$

求二次剩余的平方根

模数	主要算法
$p$	Tonelli-Shanks
$p^k$	Hensel lifting
$n$	已知因子分解：中国剩余映射/定理；未知因子：高效算法未知

---

勒让德符号

定义：$设p是奇素数，整数a满足gcd(a,p)=1,则勒让德符号定义为：$

$$(\frac {a}{p}):=\begin{cases}1,&{a\in (Z_p^*)^2}\\[4ex]{-1},&{a\in (Z_p^*)\setminus(Z_p^*)^2}\end{cases}$$

$且如果p\mid a,则令(\frac {a}{p})=0$

性质:$设p是奇素数，a,b\in Z,则有$

• $1.\ (\frac {a}{p})\equiv a^{\frac{p-1}2}\pmod p；特别地，(\frac {-1}{p})= (-1)^{\frac{p-1}2}$

• $2.\ (\frac {a}{p})(\frac {b}{p})=(\frac {ab}{p})$

• $3.\ a\equiv b\pmod p \Rightarrow (\frac {a}{p})=(\frac {b}{p})$

• $4.\ (\frac {2}{p})=(-1)^{\frac{p^2-1}{8}}\ \ \ \ \ \ 2\in(Z_p^*)^2\iff p\equiv \pm 1\pmod 8$

• $5.\ 二次互反律(使用前要检查是否存在模4余1)：设p、q是奇素数，则有(\frac {p}{q})=(-1)^{ {\frac{p-1}2}{\frac{q-1}2} }(\frac {q}{p})$

  $若p\equiv 1\pmod 4\ or\ q\equiv 1\pmod 4\iff (\frac {p}{q})=(\frac {q}{p}),反之则(\frac {p}{q})=-(\frac {q}{p})$

---

雅可比符号

定义：$设a是整数，n是正整数，n=p_1\dots p_t，其中p_i都是奇素数(彼此可以相等)，则雅可比符号定义为：$

$(\frac {a}{n})=(\frac {a}{p_1})\dots (\frac {a}{p_t})\ 且令(\frac {a}{1})=1$

$gcd(a,n)>1\iff (\frac{a}{n})=0$

性质:$设m和n是正奇数，a,b\in \mathbb{Z},则有$

• $1.\ \ (\frac {-1}{n})\equiv {(-1)}^{\frac{n-1}2}$

• $2.\ (\frac {a}{n})(\frac {b}{n})=(\frac {ab}{n})$

• $3.\ a\equiv b\pmod n \Rightarrow (\frac {a}{n})=(\frac {b}{n})$

• $4.\ (\frac {2}{n})=(-1)^{\frac{n^2-1}{8}}$

• $5.\ (\frac {a}{mn})=(\frac {a}{m})(\frac {a}{n})$

• 二次互反律的推广：

  $(\frac {m}{n})={(-1)}^{ {\frac{m-1}2}{\frac{n-1}2} }(\frac {n}{m})$

  $若m\equiv 1\pmod 4\ or\ n\equiv 1\pmod 4\iff (\frac {m}{n})=(\frac {n}{m}),反之则(\frac {m}{n})=-(\frac {n}{m})$

• 能否判断二次剩余？

  $(\frac{a}{n})=0或-1\Rightarrow a\notin (Z_n^*)^2$

  $(\frac{a}{n})=1\Rightarrow 无法判断$

  $a\in (Z_n^*)^2\Rightarrow (\frac{a}{n})=1$

---

雅可比映射(Jacobi map)

$J_n:Z_n^*\rightarrow{\pm1}$

$a\in Z_n^*\rightarrow (\frac{a}{n})=\pm1$

$雅可比映射的核：Ker\ J_n：Z_n^*中映射到1的部分形成的一个子集$

二次剩余性假设(QR假设,Quadratic residuosity assumption)

$$设n=pq，其中p和q是不同的素数，\\在不知道p和q的情况下，\\给定\mathbb{Z_n^*}中的其中一个整数，(从\mathbb{Ker\ J_n}里随机选择一个整数）\\将难以判断他是不是二次剩余(难以区分二次剩余和二次非剩余,\\即难以区分它属于\mathbb{(Z_n^*)^2}还是\mathbb{Ker\ J_n\setminus (Z_n^*)^2}。$$

$(\frac{a}{n})=-1\Rightarrow a是模n下二次非剩余$

$(\frac{a}{n})=1时,(\frac{a}{p})、(\frac{a}{q})可能同为1或-1，仅前者才是二次剩余$

---

半素数（semi-prime）

定义：又称“二素数”（biprime），则$n$是半素数，则$n=pq$ ,$p$和$q$
都是$n$的素因子 ($p$和$q$可以相同)。比如：4,6,9,10,$\cdots$

Blum整数是一种半素数👇

Blum整数

定义：$n是Blum整数，则n=pq，p\equiv q\equiv 3\pmod 4$是两个不同的素因子。

性质：设n是Blum整数

• 1.$(\frac{-1}{p})=(\frac{-1}{q})=-1\\(\frac{-1}{n})=(\frac{-1}{p})(\frac{-1}{q})=(-1)(-1)=1$

• 2.$对于任意 a \in Z_{n}^{*},\left(\frac{a}{n}\right)=1 \Rightarrow a \in\left(Z_{n}^{*}\right)^{2} 或 -a \in\left(Z_{n}^{*}\right)^{2}$

  $\left(\frac{a}{n}\right)=\left(\frac{a}{p}\right)\left(\frac{a}{q}\right)=1 \Rightarrow\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)=1 或 \left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)=-1 $

  $\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)=1 \Rightarrow a \in\left(Z_{n}^{*}\right)^{2}时：$

  $$\left(\frac{-a}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{a}{p}\right)=-1 \times 1=-1 , 同理, \left(\frac{-a}{q}\right)=-1 \Rightarrow-a \in Z_{n}^{*} \backslash\left(Z_{n}^{*}\right)^{2}$$

  $\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)=-1时同理可得-a \in\left(Z_{n}^{*}\right)^{2}$

• 3.对于任意$a\in(Z_n^*)^2$,设它的四个平方根为$\pm b$和 土$b^\prime$,则

$\left(\frac bp\right)=\left(\frac bq\right)=1$,即$b\in(Z_n^*)^2$

$\left(\frac{-b}p\right)=\left(\frac{-b}q\right)=-1$

$\left(\frac{b^{\prime}}p\right)=1,\left(\frac{b^{\prime}}q\right)=-1$
$\left(\frac{-b^{\prime}}p\right)=-1,\:\left(\frac{-b^{\prime}}q\right)=1$

• 4.函数$f(x)=x^2mod$ $n$是定义在$(Z_n^*)^2$上的置换。

  $$x\in(Z_n^*)^2\Rightarrow f(x)=x^2\:mod\:n\in(Z_n^*)^2$$ $$f(x)=y\in(Z_n^*)^2\Rightarrow$有唯一的平方根 $x\in(Z_n^*)^2$$

• 5.设$a\in(Z_n^*)^2$,雅可比符号是1的两个平方根中只有一个小于$\frac n2$ (另一个大于$\frac n2)$。

  暗示：雅可比符号是 -1 的两个平方根中只有一个的值小于 $\frac n2$ (另一个大于$\frac n2)$
  取值小于 (大于)$\frac n2$的两个平方根的雅可比符号互为相反数。

---

连分数（Continued Fraction）

简单连分数(Simple Continued Fraction)

$a_0+\frac1{a_1+\frac1{a_2+\frac1{a_3+\frac1{…}}}}$
$a_0$可以是任意整数，$a_i$是正整数$(i>0):$部分商 (partial quotient)
$[a_0,a_1,a_2,a_3,…]$

例：$\frac{43}{19}= 2+\frac1{3+\frac1{1+\frac14}}=[2,3,1,4]=[2,[3,1,4]]=2+\frac{1}{[3,1,4]}$

任何实数都可以用连分数的形式来表示

$\mathbb{Q}=\{\frac ab\mid a,b\in\mathbb{Z},b\neq0\}$

有限连分数(Finite Continued Fraction)

$[a_0,a_1,\dots,a_n]$

定理：任何有理数都可以表示成有限连分数；任何
有限连分数都是一个有理数。
$\frac ab\ \underleftrightarrow{欧几里得算法}\ [a_0,a_1,…,a_n]$

$[a_0,a_1,\dots,a_n]=[a_0,a_1,\dots,a_m,[a_{m+1}\dots,a_n]]$

有限连分数表示倒数

给定有限连分数$[a_0,a_1,…,a_n]$,求倒数

• 如果$a_0=0$,就把0去掉：$[a_1,…,a_n]$
• 如果$a_0\neq0$,就在前面补上$0:[0,a_0,…,a_n]$

有限连分数的等价表示

$n> 0$,$a_n=1$时，$[a_0,a_1,…,1]=[a_0,a_1,…,a_{n-1}+1]$
否则，$[a_0,a_1,…,a_n]=[a_0,a_1,…,a_n-1,1]$

唯一性表达

定理：如果两个有限连分数$[a_0,…,a_n],[b_0,…,b_m]$都等于有理数$x$,并且$a_n>1,b_m>1$,那么$n=m$,而且它俩是完全相同的。

无限连分数(Infinite Continued Fraction)

$[a_0,a_1,\dots]$

表示无理数

定理1：对于无限连分数$[ a_0, a_1, . . . ]$, $x_n= [ a_0, a_1, . . . , a_n]$是第n个渐进分数。如果$n\to\infty$,则$x_n\to x$ , $x\in R$ 。
$x=[a_0,a_1,\dots]$

渐进分数的分母满足以下性质：
第n个渐进分数$[a_0,a_1,…,a_n]=x_n=\frac{p_n}{q_n}$ ,
则 $q_n\geq n$。如果$n>3$,则 $q_n>n$。(证明略)

性质：

• 任何无限连分数都小于它的任意奇数编号的渐进分数，而大于任意偶数编号的。(三明治结构)
• $a_t$是第$t$个完全商的整数部分。特别的，$a_0$是无限连分数的整数部分。
• 两个无限连分数，如果它们表示的实数相同、它俩就是完全相同的。
• 任何无理数表示成无限连分数时，其表示形式是唯一的。

渐进分数

定义：$\begin{aligned}\text{称 }&[a_0,…,a_m]\left(0\leq m\leq n\right)\text{为 }[a_0,a_1,…,a_n]\text{的第m个渐进分数。}\end{aligned}$

普遍规律：原本的分数居中，偶数编号位于左边，呈递增趋势，奇数编号位于右边，呈递减趋势，从两边逐渐逼近。

$[a_0]=\frac{p_0}{q_0}$
$[a_0,a_1]=\frac{p_1}{q_1}$
$[a_0,a_1,…,a_n]=\frac{p_n}{q_n}$
$\frac{p_0}{q_0}<\frac{p_2}{q_2}<\cdots<\frac{p_n}{q_n}<\cdots<\frac{p_3}{q_3}<\frac{p_1}{q_1} $

迭代公式

写成$[a_0,…,a_m]=\frac{p_n}{q_n}$
则有$p_n=a_np_{n-1}+p_{n-2},\quad q_n=a_nq_{n-1}+q_{n-2}\quad(n\geq2)$

定理

$p_n q_{n-1}-p_{n-1} q_n=(-1)^{n-1}$

完全商(Complete quotient)

定义：称$[a_t,\dots,a_n](0≤t\leq n)为[a_0,a_1,...,a_n]的第t个完全商$

定理：$\text{定理:给定有限连分数 }[a_0,a_1,…,a_n]\text{,有}$

$\bullet\text{ 如果 }a_n=1\text{,则 }[a_{n-1},a_n]\text{ 的整数部分是 }a_{n-1}+1$

$\bullet\text{ 否则 }[a_t,…,a_n]\text{ (0}\leq t\leq n)\text{ 的整数部分是 }a_t$

单调性（monotone properties）

• 性质1：所有偶数编号的渐进分数是严格递增的($\frac{p_0}{q_0}<\frac{p_2}{q_2}<\cdotp\cdotp\cdotp)$,而奇数编号的则是严格递减的($…<\frac{p_3}{q_3}<\frac{p_1}{q_1}).$

• 性质2：任何奇数编号的渐进分数大于和它相邻的两个偶数编号的渐进分数。

• 性质3：$\frac{p_0}{q_0}<\frac{p_2}{q_2}<\cdots<\frac{p_n}{q_n}<\cdots<\frac{p_3}{q_3}<\frac{p_1}{q_1} $

  如果$n$是偶数，则$x_n$是偶数编号里最大的渐进分数，
  且 $x_n$小于所有奇数编号的渐进分数。

  如果$n$是奇数，则$x_n$是奇数编号里最小的渐进分数，

  且 $x_n$大于所有偶数编号的渐进分数。

连分数算法 (continued fraction algorithm)

欧几里得算法只能处理分数，不能处理小数

输入：实数$x$

令$i=0,x_0=x;$

• step1. 令$a_i$为 $x_i$的整数部分；
• step2. $b_i=x_i-a_i$
• step3. $ if\ b_i\neq0$, then $i++,x_i=1/_{b_i}$,$转去step1$;
• else return $[a_0,a_1,…]$ ;

周期连分数(periodic continued fraction)

定义：周期连分数$[a_0,a_1,…]$是无限连分数，而且对于固定的正整数$k$,以及所有的$l\geq L$,
都有$a_l=a_{l+k}$ ,
部分商$a_L,…,a_{L+k-1}$称作 周期(period)。

可简写成$\left[a_0,…,a_{L-1},\overline{a_L,…,a_{L+k-1}}\right]$。

例：$\begin{aligned}&[2,5,1,4,3,6,1,4,3,6,…]\\&=[2,5,\overline{1,4,3,6}]\end{aligned}$

一元二次方程

$$ax^2+bx+c=0\quad(a,b,c\in\mathbb{Z},\:a\neq0)$$

二次不尽根$: u\pm \sqrt {w}$ $( u, w\in Q)$ ,$\sqrt{w}$ 是无理数 ($w$不能完全开方）

• 定理(欧拉):如果t是周期连分数，它就一定是二次不尽根
• 定理(拉格朗日):如果t是二次不尽根，它就一定是周期连分数

$$\begin{aligned}x^2-2x-1&=0\\x^{2}&=2x+1\\x&=2+\frac1x\\&=2+\frac1{2+\frac1x}\\&=2+\frac{1}{2+{\frac{1}{\dots}}}=[2,2,\dots]=1+\sqrt{2}(白银比例)\end{aligned}$$ $$\begin{aligned}x^2-x-1&=0\\x^{2}&=x+1\\x&=1+\frac1x\\&=1+\frac1{1+\frac1x}\\&=1+\frac{1}{1+{\frac{1}{\dots}}}=[1,1,\dots]=\frac{1+\sqrt{5}}2(黄金比例)\end{aligned}$$

周期连分数与数列

斐波那契数列 $1,1,2,3,5,8,13,\dots$

$F_0=1,\quad F_1=1,$
$F_n=F_{n-1}+F_{n-2}=\frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}\quad(\phi=\frac{1+\sqrt{5}}2)$

• 黄金比例的周期连分数的各个渐进分数恰好是斐波那契数列相邻两项相除所得的分数

佩尔数列 $0,1,2,5,12,29,70,\dots$

$P_0=0,P_1=1,$

$P_n=2P_{n-1}+P_{n-2}=\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$

• 白银比例的周期连分数的各个渐进分数恰好是佩尔数列相邻两项相除所得的分数

最佳近似值&丢番图逼近(Diophantine approximation)

最佳近似值定义：在数轴上，如果与其他有理数相比，$\frac pq$ ($p$和$q$ 没有公因子)到实数$x$ 的距离更近，那么$\frac pq$就叫作$x$ 的最佳近似值(只考虑分母大小不超过q的有理数)

定理：$\text{设 }x=[a_0,a_1,…]\text{,在分母不超过 }q_t\text{ 的有理数中,}\\\text{第}t\text{个渐进分数 }\frac{p_t}{q_t}\text{ 是 实数 }x\text{ 的最佳近似值。}$(证明略)

一个实数所有的渐进分数都是他的最佳近似值(分母不超过渐进分数的分母的全部有理数范围内)

实数的最佳近似值不只有它的渐进分数

半渐进分数(semi-convergent)(次渐进分数(secondary convergent))

定义：设 $x=[a_0,a_1,…],\frac{p_t}{q_t}$ 和$\frac{p_{t+1}}{q_{t+1}}$是x的两个相邻的渐进分数，则
$\frac{p_t\:+\:r\:p_{t+1}}{q_t\:+\:r\:q_{t+1}}\quad(r\in\mathbb{Z},\:0\leq r\leq a_t)$,称作$x$的半渐进分数。

• 渐 进 分 数 也 是 半 渐 进 分 数

• 实数的最佳近似值只存在于半渐进分数里第t个和第t+2个渐进分数之间，大约有一半的“半渐进分数”是最佳近似值

• $a^t$可以用来度量“逼近”的程度，表示渐进分数离实数究竟有多近。
  $a^t$越大，渐进分数就更逼近实数。

连分数的相反数

简单连分数中，只有$a_0$可为非正整数(0,$\pm$)

简单连分数表示负数

给实数

$$x=-X-F(0<F<1)\\=(-X-1)+(1-F)\\=[a_0-X-1,a_1,...]$$

$1-F=[a_0,a_1,…]$

给简单连分数

$x=[a_0,a_1,a_2,…]$

$-x=[-a_0-1,1,a_1-1,a_2,…]$

PS:$若中间出现0，[...,a_{t-1},a_t,0,a_{t+1},a_{t+2},...],则-x=[...,a_{t-1},a_t+a_{t+1},a_{t+2},...]$

$$若末尾出现0，[\ldots,a_{n-2},a_{n-1},0],则-x=[\ldots,a_{n-2}]$$

普通连分数(general continued fraction)

$a_0+\frac{b_1}{a_1+\frac{b_2}{a_2+\frac{b_3}{…}}}$
$b_i$是正整数

连分数的应用

天文历法，植物学上树叶在茎上的排列规律，音乐领域

密码学上，著名的RSA算法

---

完结撒花

★,°:.☆(￣▽￣)/$:.°★ 。*爱来自😽C.A.T😸喵