| layout | title | date | categories | tags | comments | mathjax | mermaid | copyrights | recommend |
|---|---|---|---|---|---|---|---|---|---|
post |
网络空间安全数学基础笔记 |
2020-04-01 00:00:00 +0800 |
数学 |
note math group |
true |
true |
true |
原创 |
true |
本文为网络空间安全数学基础笔记。
-
Eratoshenes筛法
对任意给定的正整数
$$N$$ ，要求出所有不超过$$N$$ 的素数，列出$$N$$ 个整数，从中删除不大于$$\sqrt{N}$$ 的所有素数的倍数，将其依次删除，余下的整数就是所要求的不超过$$N$$ 的素数 -
整数分解
寻求
$$n=(s+t)(s-t)$$
广义欧几里得除法
$$j$$ $$r_j$$ $$r_{j+1}$$ $$q_{j+1}$$ $$r_{j+2}$$ $$0$$ $$a$$ $$b$$ $$a/b$$ $$a\mod b$$ $$\cdots$$ $$\cdots$$ $$\cdots$$ $$\cdots$$ $$\cdots$$ $$n$$ $$\cdots$$ $$(a,b)$$ $$\cdots$$ $$0$$
广义欧几里得除法
$$j$$ $$s_j$$ $$t_j$$ $$q_{j+1}$$ $$r_{j+1}$$ $$-3$$ $$a$$ $$-2$$ $$1$$ $$0$$ $$b$$ $$-1$$ $$0$$ $$1$$ $$q_0$$ $$r_0$$ $$0$$ $$s_0$$ $$t_0$$ $$q_1$$ $$r_1$$ $$\cdots$$ $$\cdots$$ $$\cdots$$ $$\cdots$$ $$\cdots$$ $$n$$ $$s_n$$ $$t_n$$ $$q_{n+1}$$ $$r_{n+1}=0$$
$$ \left{\begin{array}{lr}s_j=(-q_j)s_{j-1}+s_{j-2}&\t_j=(-q_j)t_{j-1}+t_{j-2}&\q_{j+1}=\left[\frac{r_{j-1}}{r_j}\right]&\r_{j+1}=(-q_{j+1})r_j+r_{j-1} \end{array}\right.$$
-
计算
$$[a,b]=\frac{a\cdot b}{(a,b)}$$ -
多个整数
- 递归法
- 算术基本定理
STEP1: 判断有解
若
$$(a,b)\mid c$$ ，则有解STEP2: 求一个解
贝祖等式得到
$$s$$ 和$$t$$ ，则$$x_0=\frac{c}{(a,b)}s, y_0=\frac{c}{(a,b)}t$$ STEP3: 求所有解
计算
$$x=x_0+\frac{b}{(a,b)}n, y=y_0-\frac{a}{(a,b)}n$$
- 概念解释
| 符号/概念 | 定义 |
|---|---|
| 模 |
|
|
|
|
| 模 |
|
| 剩余 | 一个剩余类中的任一数 |
| 简化剩余类 | |
| $$F_{p}^{}={\left(Z/pZ\right)}^{}$$ |
|
-
定理
-
设
$$m$$ 是一个正整数，$$a$$ 是满足$$(a, m)=1$$ 的整数。如果$$k$$ 遍历模$$m$$ 的一个简化剩余系，则$$a\cdot k$$ 也遍历模$$m$$ 的一个简化剩余系 -
设
$$m_1,m_2$$ 是互素的两个正整数。如果$$k_1,k_2$$ 分别遍历模$$m_1$$ 和模$$m_2$$ 的简化剩余系，则$$k_3=m_2\cdot k_1+m_1\cdot k_2$$ 遍历模$$m_1\cdot m_2=12$$ 的简化剩余系
-
设
-
对于素数幂
$$m=p^\alpha$$ ，有$$\varphi(m)=p^\alpha-p^{\alpha-1}$$ -
有
$$\lvert{\left(Z/mZ\right)}^{*}\rvert=\varphi(m)$$ -
若
$$(m,n)=1$$ ，则$$\varphi(m\cdot n)=\varphi(m)\cdot \varphi(n)$$ -
若
$$m=p_{1}^{\alpha_1}p_{2}^{\alpha_2}\cdots p_{s}^{\alpha_s}$$ ，则$$\varphi(m)=m\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_s}\right)$$ -
若
$$p,q$$ 为两个素数，则$$\varphi(p\cdot q)=p\cdot q-p-q+1$$ -
有
$$\sum_{d\mid m}{\varphi(d)}=m$$
-
欧拉定理
若
$$(a,m)=1$$ ，则$$a^{\varphi(m)}\equiv1 \left(\mod m\right)$$ -
费马小定理
若
$$p$$ 为素数，则$$a^{p}\equiv a \left(\mod p\right)$$ -
Wilson定理
若
$$p$$ 为素数，则$$\left(p-1\right)!\equiv -1 \left(\mod p\right)$$
STEP1: 将$$n$$写成二进制
$$n=n_0+n_1 2+\cdots+n_{k-1}2^{k-1}$$ STEP2: 计算
$$a=1$$ $$\left{ \begin{array}{lr} a_0\equiv a\cdot b^{n_0}\left(\mod m\right), b_1\equiv b^2\left(\mod m\right)\ a_1\equiv a_0\cdot b_{1}^{n_1}\left(\mod m\right), b_2\equiv b_{1}^{2}\left(\mod m\right)\ \cdots\ a_{k-2}\equiv a_{k-3}\cdot b_{k-2}^{n_{k-2}}\left(\mod m\right), b_{k-1}\equiv b_{k-2}^{2}\left(\mod m\right)\ a_{k-1}\equiv a_{k-2}\cdot b_{k-1}^{n_{k-1}}\left(\mod m\right) \end{array} \right.$$
$$a_{k-1}$$ 即为$$b^n\left(\mod m\right)$$
原理：利用大整数分解的困难性
- 公钥(加密)：$$\left(e,n\right)$$
- 私钥(解密)：$$\left(d,n\right)$$
加密
$$E\left(P\right)=C\equiv P^e\left(\mod n\right)$$
准备好
$$p,q$$ ，计算$$n=p\cdot q,\varphi\left(n\right)$$ 假设一个与
$$\varphi\left(n\right)$$ 互质的$$e$$ ，求出$$d$$ 使用公钥加密信息
$$m$$ ：$$m^e\equiv c\left(\mod n\right)$$解密
$$D\left(C\right)=C^d\equiv {\left(P^e\right)}^{d}\equiv P^{e\cdot d}$$
$$\equiv P^{k\cdot\varphi\left(n\right)+1}\equiv\left(P^{\varphi\left(n\right)}\right)P\equiv P\left(\mod n\right)$$
- 求解
$$c^d\left(\mod n\right)$$
-
一次同余式有解
$$a\cdot x\equiv b\left(\mod m\right)$$ 有解$$\Longleftrightarrow\left(a,m\right)\mid b$$ $$x\equiv \frac{b}{\left(a,m\right)}\cdot\left({\left(\frac{a}{\left(a,m\right)}\right)}^{-1}\left(\mod \frac{m}{\left(a,m\right)}\right)\right)+t\cdot\frac{m}{\left(a,m\right)}\left(\mod m\right)$$ $$t=0,1,\cdots,\left(a,m\right)-1$$ -
一次同余式求解
STEP1: 验证有解
STEP2: 求解
$$\frac{a}{\left(a,m\right)}\cdot x\equiv 1\left(\mod \frac{m}{\left(a,m\right)}\right)$$ 广义欧几里得除法得到特解
$$x_{0}^{\prime}\equiv c\left(\mod \frac{m}{\left(a,m\right)}\right)$$ STEP3: 求同余式
$$\frac{a}{\left(a,m\right)}\cdot x\equiv \frac{b}{\left(a,m\right)}\left(\mod \frac{m}{\left(a,m\right)}\right)$$ 得到特解
$$x_0\equiv \frac{b}{\left(a,m\right)}\cdot x_{0}^{\prime}\equiv \frac{b}{\left(a,m\right)}\cdot c\equiv d\left(\mod \frac{m}{\left(a,m\right)}\right)$$ STEP4: 写出全部解
$$x\equiv d+t\cdot\frac{m}{\left(a,m\right)}\left(\mod m\right),t=0,1,\cdots,\left(a,m\right)-1$$
令
$$m=m_1\cdot m_2\cdots m_k=m_i\cdot M_i$$ 计算
$$M_{i}^{\prime}\cdot M_i\equiv1\left(\mod m_i\right), i=1,\cdots,k$$ 再计算
$$x\equiv \sum\limits_{i=1}^{k}{b_i\cdot M_{i}^{\prime}\cdot M_i}\left(\mod m\right)$$
STEP1: 分解
$$m$$
$$m=m_1\cdots m_k$$ STEP2: 欧拉定理
$$ \left{ \begin{array}{lr} a^{n_1}\equiv 1\left(\mod m_1\right) &\ \vdots &\ a^{n_k}\equiv 1\left(\mod m_k\right) \end{array} \right. \Longrightarrow \left{ \begin{array}{lr} a^{n}\equiv b_1\left(\mod m_1\right) &\ \vdots &\ a^{n}\equiv b_k\left(\mod m_k\right) \end{array} \right. $$
STEP3: 利用中国剩余定理求解
$$a^n\equiv b\left(\mod m\right)$$
应用：
- RSA解密加速
- 残差数字系统
-
高次同余式解数
若
$$m=m_1\cdots m_k$$ ，则同余式$$f\left(x\right)\equiv0\left(\mod m\right)$$ 与同余式组$$ \left{ \begin{array}{lr} f\left(x\right)\equiv 0\left(\mod m_1\right) &\ \vdots &\ f\left(x\right)\equiv 0\left(\mod m_k\right) \end{array} \right. $$
等价。若
$$T_i$$ 为同余式$$f\left(x\right)\equiv 0\left(\mod m_i\right)$$ 的解数，则同余式解数$$T=T_1\cdots T_k$$ -
高次同余式求解
$$f\left(x\right)\equiv0\left(\mod p^\alpha\right)$$
STEP1: 验证有解
$$x=x_1\left(\mod p\right)$$ 为$$f\left(x\right)\equiv0\left(\mod p\right)$$ 的一个解，$$\left(f^\prime\left(x_1\right),p\right)=1$$STEP2: 递推
$$x\equiv x_\alpha\left(\mod p^\alpha\right)$$ $$ \left{ \begin{array}{lr} t_{i-1}\equiv-\frac{f\left(x_{i-1}\right)}{p^{i-1}}\cdot\left({f^\prime\left(x_1\right)}^{-1}\left(\mod p\right)\right)\left(\mod p\right) &\ x_i\equiv x_{i-1}+t_{i-1}\cdot p^{i-1}\left(\mod p^i\right) &\ i=2,\cdots,a \end{array} \right. $$
$$f\left(x\right)=q\left(x\right)\left(x^p-x\right)+r\left(x\right)$$
$$f\left(x\right)\equiv0\left(\mod p\right)\Longleftrightarrow r\left(x\right)\equiv0\left(\mod p\right)$$
-
一般二次同余式化简
$$ax^2+bx+c\equiv 0\left(\mod m\right),a\not\equiv0\left(\mod m\right)$$
$$m=p_{1}^{\alpha_1}\cdots p_{k}^{\alpha_k}$$
$$ \left{ \begin{array}{lr} ax^2+bx+c\equiv 0\left(\mod p_{1}^{\alpha_!}\right) &\\ \vdots &\\ ax^2+bx+c\equiv 0\left(\mod p_{k}^{\alpha_k}\right) \end{array} \right. $$
-
素数幂的同余式化简
$$ax^2+bx+c\equiv 0\left(\mod m\right),a\not\equiv0\left(\mod m\right)$$ $$p$$ 为奇素数，$$\left(2a,p\right)=1$$
STEP1: 两端同时乘以
$$4a$$ STEP2:
$${\left(2ax+b\right)}^2\equiv b^2-4ac\left(\mod p^{\alpha}\right)$$ STEP3: 令
$$y=2ax+b$$ ，有$$y^2\equiv b^2-4ac\left(\mod p^{\alpha}\right)$$
即简化为
-
定义
$$m$$ 为正整数，若$$x^2\equiv a\left(\mod m\right),\left(a,m\right)=1$$ 有解，则$$a$$ 为$$m$$ 的二次剩余，否则为二次非剩余 -
欧拉判别条件
$$p$$ 为奇素数，$$\left(a,p\right)=1$$-
$$a$$ 是模$$p$$ 的平方剩余$$\Longleftrightarrow a^{\frac{p-1}{2}}\equiv1\left(\mod p\right)$$ -
$$a$$ 是模$$p$$ 的非平方剩余$$\Longleftrightarrow a^{\frac{p-1}{2}}\equiv-1\left(\mod p\right)$$
推论：
-
$$p$$ 为奇素数，$$\left(a_1,p\right)=1,\left(a_2,p\right)=1$$，则$$a_1\cdot a_2$$ 为模$$p$$ 的平方非剩余$$\Longleftrightarrow a_1,a_2$$ 同为模$$p$$ 的平方剩余或平方非剩余 -
平方剩余与平方非剩余数量相等
-
-
定义
$$p$$ 为素数$$ \left(\frac{a}{p}\right)=\left{ \begin{array}{lr} 1 &a为模p的平方剩余\ -1 &a为模p的非平方剩余\ 0 &p\mid a \end{array} \right. $$
-
欧拉判别法则
$$p$$ 为奇素数，对整数$$a$$ $$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\left(\mod p\right)$$ -
性质
-
$$\left(\frac{1}{p}\right)=1$$ -
$$\left(\frac{-1}{p}\right)={\left(-1\right)}^{\frac{p-1}{2}}$$ -
$$p$$ 为奇素数，则-
$$\left(\frac{a+p}{p}\right)=\left(\frac{a}{p}\right)$$ -
$$\left(\frac{a\cdot b}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$ -
设
$$\left(a,p\right)=1$$ ，则$$\left(\frac{a^2}{p}\right)=1$$
-
-
-
高斯引理
$$p$$ 为奇素数，$$a$$ 为整数，$$\left(a,p\right)=1$$，整数$$a\cdot1,a\cdot2,\cdots,a\cdot\frac{p-1}{2}$$ 中模$$p$$ 的最小正剩余大于$$\frac{p}{2}$$ 的个数是$$m$$ ，则$$\left(\frac{a}{p}\right)={\left(-1\right)}^m$$
METHOD1: 定理
设
$$p$$ 为奇素数
$$\left(\frac{2}{p}\right)={\left(-1\right)}^{\frac{p^2-1}{8}}$$ 若
$$\left(a,2p\right)=1$$ ，则$$\left(\frac{a}{p}\right)={\left(-1\right)}^{T_{\left(a,p\right)}}$$ ，其中$$T_{\left(a,p\right)}=\sum_\limits{k=1}^{\frac{p-1}{2}}{\left[\frac{a\cdot k}{p}\right]}$$ METHOD2: 二次互反律
若
$$p,q$$ 为互素奇素数，则$$\left(\frac{p}{q}\right)={\left(-1\right)}^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\left(\frac{p}{q}\right)$$
-
定义 设
$$m=p_1\cdots p_r$$ 是奇素数$$p_i$$ 的乘积$$\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)\cdots\left(\frac{a}{p_r}\right)$$ $$ \left(\frac{a}{m}\right)=\left{ \begin{array}{lr} -1 &可判断a是模m平方非剩余\ 1 &不可判断a是模m平方剩余 \end{array} \right. $$
-
性质
-
若
$$m=p_1\cdots p_r$$ 是奇数-
$$\left(\frac{a+m}{m}\right)=\left(\frac{a}{m}\right)$$ -
$$\left(\frac{a\cdot b}{m}\right)=\left(\frac{a}{m}\right)\left(\frac{b}{m}\right)$$ -
设
$$\left(a,m\right)=1$$ ，则$$\left(\frac{a^2}{m}\right)=1$$ -
$$\frac{m-1}{2}\equiv \frac{p_1-1}{2}+\cdots\frac{p_r-1}{2}\left(\mod 2\right)$$ -
$$\frac{m^2-1}{2}\equiv \frac{p_1^2-1}{2}+\cdots\frac{p_r^2-1}{2}\left(\mod 2\right)$$ -
$$\left(\frac{1}{m}\right)=1$$ -
$$\left(\frac{-1}{m}\right)={\left(-1\right)}^{\frac{m-1}{2}}$$ -
$$\left(\frac{2}{m}\right)={\left(-1\right)}^{\frac{m^2-1}{8}}$$
-
-
若
$$m,n$$ 均为奇数$$\left(\frac{n}{m}\right)={\left(-1\right)}^{\frac{m-1}{2}\cdot\frac{n-1}{2}}\left(\frac{m}{n}\right)$$
-
-
模
$$4k+3$$ 平方根$$p$$ 为形如$$4k+3$$ 的素数，求同余式$$x^2\equiv a\left(\mod p\right)$$
STEP1: 二次互反律验证有解
$$a^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\equiv 1\left(\mod p\right)$$ STEP2: 定理
解为
$$x\equiv \pm a^{\frac{p+1}{4}}\left(\mod p\right)$$
-
模
$$4k+1$$ 平方根$$p$$ 为奇素数，$$p-1=2^t\cdot s$$，$$t\geq 1$$，$$s$$ 为奇数，求同余式$$x^2\equiv a\left(\mod p\right)$$
STEP1: 验证有解
STEP2: 求解
$$b$$ 和$$a^{-1}$$
$$n$$ 为模$$p$$ 的平方非剩余，$$b=n^s\left(\mod p\right)$$STEP3: 求解
$$x_{t-1}\equiv a^{\frac{s+1}{2}}\left(\mod p\right)$$ $$ j_{k-1}=\left{ \begin{array}{lr} 0 &{\left(a^{-1}x_{t-k}^{2}\right)}^{2^{t-k-1}}\equiv1\left(\mod p\right)\ 1 &{\left(a^{-1}x_{t-k}^{2}\right)}^{2^{t-k-1}}\equiv -1\left(\mod p\right) \end{array} \right. $$
$$x_{t-k-1}=x_{t-k}b^{j_{k-1}2^{k-1}}$$
$$x_0$$ 为解
-
模$$m$$平方根
$$m=2^{\delta}\cdot p_{1}^{\alpha_1}\cdots p_{k}^{\alpha_k}$$
STEP1: 等价同余式组
原同余式等价于
$$ \left{ \begin{array}{lr} x^2\equiv a\left(\mod 2^{\delta}\right)\ x^2\equiv a\left(\mod p_{1}^{\alpha_1}\right)\ \cdots\ x^2\equiv a\left(\mod p_{k}^{\alpha_k}\right) \end{array} \right. $$
STEP2: 求
$$x^2\equiv a\left(\mod p^{\alpha}\right)$$
求
$$x^2\equiv a\left(\mod p\right)$$ 若
$$\alpha>1$$ ，使用高次同余式求解方法求$$x^2-a\equiv0\left(\mod p^{\alpha}\right)$$ 有解的条件及个数STEP3: 求
$$x^2\equiv a\left(\mod 2^{\alpha}\right)$$
验证有解
$$ \left{ \begin{array}{lr} a\equiv 1\left(\mod 4\right) &\alpha=2\ a\equiv 1\left(\mod 8\right) &\alpha\geq3 \end{array} \right. $$
求解
$$\alpha=2$$
$$x\equiv\pm1\left(\mod 4\right)$$
$$\alpha=3$$
$$x\equiv\pm1,\pm3\left(\mod 8\right)$$
$$\alpha\geq4$$ 若同余式
$$x^2\equiv a\left(\mod 2^{\alpha-1}\right)$$ 的解为$$x=\pm\left(x_{\alpha-1}+t_{\alpha-1}2^{\alpha-2}\right),t_{\alpha-1}=0,\pm1,\cdots$$
$$x^2\equiv a\left(\mod 2^{\alpha}\right)$$ 的解为$$x=\pm\left(x_{\alpha}+t_{\alpha}2^{\alpha-1}\right)=\pm\left(x_{\alpha-1}+\left(\frac{a-x_{\alpha-1}^{2}}{2^{\alpha-1}}\left(\mod2\right)\right)\cdot2^{\alpha-2}+t_{\alpha}2^{\alpha-1}\right),t_{\alpha}=0,\pm1,\cdots$$ 解为
$$x_{\alpha},x_{\alpha}+2^{\alpha-1},-x_{\alpha},-\left(x_{\alpha}+2^{\alpha-1}\right)$$ STEP4: 利用中国剩余定理求解
STEP1: 生成密钥
解密者生成2个大素数
$$p,q$$ ，计算$$n=pq$$ 加密者密钥为
$$n$$ ，解密者密钥为$$\left(p,q\right)$$ STEP2: 加密信息
$$m$$ 计算
$$c\equiv m^2\left(\mod n\right)$$ STEP3: 解密信息
求解同余式 $$\left{ \begin{array}{lr} m^2\equiv c\left(\mod p\right)\ m^2\equiv c\left(\mod q\right) \end{array} \right.$$
STEP1: 求
$$m_0$$ 寻找
$$x=x_0$$ ，使得$$x^2\equiv-1\left(\mod p\right)$$ ，存在$$y_0=1$$ 使得$$x_0^2+y_0^2=m_0\cdot p$$ STEP2:求
$$u_i, v_i$$
$$u_i\equiv x_i\left(\mod m_i\right)$$
$$v_i\equiv y_i\left(\mod m_i\right)$$ STEP3: 求
$$x_i, y_i$$
$$x_{i+1}=\frac{u_i\cdot x_i+v_i\cdot y_i}{m_i}$$
$$y_{i+1}=\frac{u_i\cdot y_i-v_i\cdot x_i}{m_i}$$ STEP4: 求
$$m_i$$
$$x_i^2+y_i^2=m_i\cdot p$$ 当
$$m_k=1$$ 时，$$x_k,y_k$$ 即为方程的解
-
定义
-
指数
设
$$m>1$$ 为整数，$$a$$ 是与$$m$$ 互素的正整数，则使得$$a^e\equiv1\left(\mod m\right)$$ 成立的最小正整数$$e$$ 叫做$$a$$ 对模$$m$$ 的指数，记作$$\mathrm{ord}_{m}{\left(a\right)}$$ -
原根
若
$$e=\varphi{\left(m\right)}$$ ，则$$a$$ 为模$$m$$ 的原根
-
-
定理
-
$$a^d\equiv1\left(\mod m\right)\Longleftrightarrow\mathrm{ord}_{m}{\left(a\right)}\mid d$$ -
设
$$p$$ 为奇素数，$$\frac{p-1}{2}$$ 为素数，若$$a\not\equiv0,1,-1\left(\mod p\right)$$ ，则$$\mathrm{ord}_{p}{\left(a\right)}=\frac{p-1}{2}$$ 或$$p-1$$ -
$$b\equiv a\left(\mod m\right)\Longrightarrow \mathrm{ord}{m}{\left(b\right)}=\mathrm{ord}{m}{\left(a\right)}$$
-
$$a^{-1}a\equiv1\left(\mod m\right)\Longrightarrow \mathrm{ord}{m}{\left(a^{-1}\right)}=\mathrm{ord}{m}{\left(a\right)}$$
-
$$1=a^0,a,\cdots,a^{\mathrm{ord}_{m}{\left(a\right)}-1}$$ -
$$a^d\equiv a^k\left(\mod m\right)\Longleftrightarrow d\equiv k\left(\mod \mathrm{ord}_{m}{\left(a\right)}\right)$$ -
$$\mathrm{ord}{m}{\left(a^d\right)}=\frac{\mathrm{ord}{m}{\left(a\right)}}{\left(d,\mathrm{ord}_{m}{\left(a\right)}\right)}$$
-
设
$$g$$ 为模$$m$$ 的原根，则$$g^d$$ 为模$$m$$ 的原根$$\Longleftrightarrow \left(d,\varphi{\left(m\right)}\right)=1$$ -
设 $$k\mid \mathrm{ord}{m}{\left(a\right)}$$，则使得 $$\mathrm{ord}{m}{\left(a^d\right)}=k,1\leq d\leq \mathrm{ord}{m}{\left(a\right)}$$ 成立的正整数 $$d$$ 满足 $$\frac{\mathrm{ord}{m}{\left(a\right)}}{k}\mid d$$，且共有
$$\varphi{\left(k\right)}$$ 个这样的$$d$$ -
模
$$m$$ 有原根$$\Longrightarrow$$ 模$$m$$ 有$$\varphi{\left(\varphi{\left(m\right)}\right)}$$ 个不同的原根 -
$$\left(\mathrm{ord}{m}{\left(a\right)},\mathrm{ord}{m}{\left(b\right)}\right)=1\Longleftrightarrow \mathrm{ord}{m}{\left(a\cdot b\right)}=\mathrm{ord}{m}{\left(a\right)}\cdot \mathrm{ord}_{m}{\left(b\right)}$$
-
-
求指数
根据
$$a^d\equiv1\left(\mod m\right)\Longleftrightarrow\mathrm{ord}_{m}{\left(a\right)}\mid d$$ ，求出$$m$$ 的因数，挨个验证
-
定理
-
模
$$p$$ 原根-
$$p$$ 为奇素数$$\Longrightarrow$$ 模$$p$$ 的原根存在，且有$$\varphi{\left(p-1\right)}$$ 个 -
$$g$$ 是模$$p$$ 的原根$$\Longleftrightarrow g^{p-1}\not\equiv1\left(\mod p^2\right)$$ 或$${\left(g+p\right)}^{p-1}\not\equiv1\left(\mod p^2\right)$$
-
-
模
$$p^{\alpha}$$ 原根-
若
$$p$$ 为奇素数，则$$g$$ 为模$$p$$ 原根$$,g^{p^{k-2}\left(p-1\right)}=1+u_{k-2}\cdot p^{k-1},\left(u_{k-2},p\right)=1\Longrightarrow g$$ 为模$$p^k$$ 原根 -
$$g$$ 为模$$p$$ 原根$$\Longrightarrow g$$ 或$$g+p$$ 为模$$p^2$$ 原根 -
$$g$$ 为模$$p^2$$ 原根$$\Longrightarrow g$$ 为模$$p^{\alpha}$$ 原根 -
$$g$$ 为模$$p^{\alpha}$$ 原根$$\Longrightarrow g$$ 与$$g+p^{\alpha}$$ 中的奇数为模$$2p^{\alpha}$$ 原根
-
-
-
求奇素数
$$p$$ 原根
STEP1: 求一个原根
$$g$$ 求出
$$p-1$$ 的所有素因数$$q_1,\cdots,q_s$$ ，则$$g$$ 是模$$p$$ 的原根$$\Longleftrightarrow \forall i,g^{\frac{p-1}{q_i}}\not\equiv1\left(\mod p\right)$$ STEP2: 求所有原根
对于
$$\left(d,\varphi\left(m\right)\right)=1$$ ，$$g^d$$ 为原根
- 求
$$p^{\alpha}$$ 原根
STEP1: 求
$$p$$ 的一个原根$$g$$ STEP2: 求
$$p^{\alpha}$$ 的原根
若
$$g^{p-1}\not\equiv1\left(\mod p^2\right)$$ ，则$$g$$ 为原根若
$${\left(g+p\right)}^{p-1}\not\equiv1\left(\mod p^2\right)$$ ，则$$g+p$$ 为原根
- 求
$$2p^{\alpha}$$ 原根
STEP1: 求
$$p^{\alpha}$$ 的一个原根$$g$$ STEP2: 求
$$2p^{\alpha}$$ 的原根
$$g$$ 与$$g+p^{\alpha}$$ 中的奇数为原根
- 模
$$m$$ 存在原根$$\Longleftrightarrow m=2,4,p^{\alpha},2p^{\alpha}$$
-
定义
设
$$m>1$$ 为整数，$$a$$ 是与$$m$$ 互素的正整数，$$g$$ 为模$$m$$ 的一个原根，则存在唯一的$$1\leq r\leq \varphi{\left(m\right)}$$ ，使得$$g^r\equiv a\left(\mod m\right)$$ ，记作$$r=\mathrm{ind}_{g}{a}$$ -
定理
-
整数
$$r$$ 满足$$g^r\equiv a\left(\mod m\right)\Longrightarrow r\equiv \mathrm{ind}_{g}{a}\left(\mod \varphi{\left(m\right)}\right)$$ -
以
$$g$$ 为底的对模$$m$$ 有相同指标$$r$$ 的所有整数全体是模$$m$$ 的一个简化剩余类 -
$$\mathrm{ind}{g}{a_1\cdots a_n}\equiv \mathrm{ind}{g}{a_1}+\cdots +\mathrm{ind}_{g}{a_n}\left(\mod \varphi{\left(m\right)}\right)$$
-
$$\mathrm{ind}{g}{a^n}\equiv n\cdot \mathrm{ind}{g}{a}\left(\mod \varphi{\left(m\right)}\right)$$
-
-
定义
设
$$m>1$$ 为整数，$$a$$ 是与$$m$$ 互素的正整数，若$$x^n\equiv a\left(\mod m\right)$$ 有解，则$$a$$ 为对模$$m$$ 的$$n$$ 次剩余 -
求解
$$x^n\equiv a\left(\mod m\right)$$
STEP1: 验证有解
$$\left(n,\varphi{\left (m\right)}\right)\mid \mathrm{ind}_{g}{a}$$ ，$$g$$ 为模$$m$$ 的原根解数为
$$\left(n,\varphi{\left (m\right)}\right)$$ STEP2: 等价同余式
等价于 $$n{\mathrm{ind}}{g}{x}\equiv \mathrm{ind}{g}{a}\left(\mod \varphi{\left (m\right)}\right)$$
STEP3: 查指标表解出
$$n{\mathrm{ind}}_{g}{x}$$ ，解出$$x\left(\mod m\right)$$
- 求解
$$n^x\equiv a\left(\mod m\right)$$
STEP1: 等价同余式
等价于 $$x{\mathrm{ind}}{g}{n}\equiv \mathrm{ind}{g}{a}\left(\mod \varphi{\left (m\right)}\right)$$
STEP2: 查指标表解出
$$x\left(\mod \varphi{\left (m\right)}\right)$$
利用离散对数对大素数取模计算的困难性：
STEP1: 获取密钥
$$\left(p,r,b\right)$$
$$p$$ : 选择一个素数$$p$$
$$r$$ :$$p$$ 的原根为$$r$$
$$a$$ : 选取整数$$a$$ ，$$0\leq a\leq p-1$$
$$b$$ :$$b\equiv r^a\left(\mod p\right)$$ STEP2: 加密信息
$$M$$
$$k$$ : 选取整数$$k$$ ，$$1\leq k\leq p-2$$
$$\gamma$$ :$$\gamma\equiv r^k\left(\mod p\right),0\leq\gamma\leq p-1$$
$$\delta$$ :$$\delta\equiv M\cdot b^k\left(\mod p\right),0\leq\delta\leq p-1$$ STEP3: 解密信息
$$\left(\gamma,\delta\right)$$
$$M\equiv \overline{\gamma^{a}}\delta\left(\mod p\right)$$
-
判断素数
$$n$$ 为素数$$\Longleftrightarrow$$ 对任意$$b,\left(b,n\right)=1$$ ，$$b^{n-1}\equiv 1\left(\mod n\right)$$ 或$${\mathrm{ord}}_{n}{\left(b\right)}\mid n-1$$ -
$$n$$ 对基$$b$$ 的伪素数$$n$$ 为奇合数，$$\left(b,n\right)=1$$，$$b^{n-1}\equiv 1\left(\mod n\right)$$-
存在无穷个对基
$$2$$ 的伪素数 -
若
$$n$$ 为对基$$b_1,b_2$$ 的伪素数，则$$n$$ 为对基$$b_1\cdot b_2$$ 的伪素数 -
若
$$n$$ 为对基$$b$$ 的伪素数，则$$n$$ 为对基$$b^{-1}$$ 的伪素数 -
若存在
$$b$$ 使得$$b^{n-1}\not\equiv 1\left(\mod n\right)$$ ，则模$$n$$ 的简化剩余系中至少有一半的的数满足$$b^{n-1}\not\equiv 1\left(\mod n\right)$$
-
-
Fermat素性检验
STEP1: 随机选取整数
$$b$$ 和安全参数$$t$$ STEP2: 计算
$$r\equiv b^{n-1}\left(\mod n\right)$$ STEP3: 若
$$r\not=1$$ ，则$$n$$ 为合数STEP4: 重复
$$t$$ 次
-
Carmichael数
合数
$$n$$ 满足对任意$$b,\left(b,n\right)=1$$ ，$$b^{n-1}\equiv 1\left(\mod n\right)$$ 存在无穷多个Carmichael数 -
证明
$$n$$ 为Carmichael数
STEP1:
$$n=p_1\cdots p_s$$ STEP2:
$$b^{p_i-1}\equiv 1\left(\mod p_i\right)$$ STEP3:
$$b^{n-1}\equiv 1\left(\mod p_i\right)$$
-
$$n$$ 对基$$b$$ 的Euler伪素数$$n$$ 为奇合数，$$\left(b,n\right)=1$$，$$b^{\frac{n-1}{2}}\equiv \left(\frac{b}{n}\right)\left(\mod n\right)$$- 若
$$n$$ 对基$$b$$ 的Euler伪素数，则$$n$$ 对基$$b$$ 的伪素数
- 若
-
Solovay-Stassen素性检验
STEP1: 随机选取整数
$$b,2\leq b\leq n-2$$ 和安全参数$$t$$ STEP2: 计算
$$r\equiv b^{\frac{n-1}{2}}\left(\mod n\right)$$ STEP3: 若
$$r\not=1$$ 且$$r\not= n-1$$ ，则$$n$$ 为合数STEP4: 计算
$$s=\left(\frac{b}{n}\right)$$ STEP5: 若
$$r\not= s$$ ，则$$n$$ 为合数STEP6: 重复
$$t$$ 次
-
$$n$$ 对基$$b$$ 的强伪素数$$n$$ 为奇合数，$$\left(b,n\right)=1$$，$$n-1=2^s t$$，$$t$$ 为奇数，$$b^t\equiv 1\left(\mod n\right)$$ 或存在$$0\leq r<s$$ 使得$$b^{2^r t}\equiv -1\left(\mod n\right)$$ -
存在无穷个对基
$$2$$ 的强伪素数 -
若
$$n$$ 对基$$b\left(1\leq b\leq n-1\right)$$ 的强伪素数可能性至多为$$25%$$
-
-
Miller-Rabin Primality素性检验
STEP1: 安全参数
$$k$$ ，$$n-1=2^s t,t$$ 为奇数STEP2: 随机选取整数
$$b,2\leq b\leq n-2$$ STEP3: 计算
$$r_0\equiv b^{t}\left(\mod n\right)$$
若
$$r_0=1$$ 或$$r_0=n-1$$ ，则通过检验，可能为素数。回到第二步否则进入下一步
STEP4: 计算
$$r_1\equiv r_{0}^{2}\left(\mod n\right)$$
若
$$r_1=n-1$$ ，则通过检验，可能为素数。回到第二步否则进入下一步
STEP5: 计算
$$r_2\equiv r_{1}^{2}\left(\mod n\right)$$
$$\vdots$$
STEPs+1: 计算
$$r_{s-1}\equiv r_{s-2}^{2}\left(\mod n\right)$$
若
$$r_{s-1}=n-1$$ ，则通过检验，可能为素数。回到第二步否则
$$n$$ 为合数
$$k$$ 次测试后，$$n$$ 为合数的概率为$${0.25}^k$$
-
梅森素数
$$M_m=2^m-1$$ 为梅森数若
$$p$$ 为素数且$$M_p=2^p-1$$ 为素数，则$$M_p$$ 为梅森素数 -
LLT
设
$$p$$ 为素数
$$r_k=r_{k-1}^{2}-2\left(\mod M_p\right),0\leq r_k\leq M_p$$ ，其中$$r_1=4,k\geq 2$$
$$r_{p-1}\equiv0\left(\mod M_p\right)\Longleftrightarrow M_p$$
METHOD1: 线性同余法
选取种子
$$x_0$$ 选取
$$m,a,c$$ ，使得$$2\leq a<m,0\leq c<m,0\leq x_0\leq m$$
$$x_{n+1}\equiv a\cdot x_n+c\left(\mod m\right)$$ METHOD2: 纯乘法同余法
选取素数
$$m$$ （通常为梅森素数$$M_{31}=2^{31}-1$$ ），$$a$$ 取其原根，最大周期长度为$$m-1$$
$$x_{n+1}\equiv a\cdot x_n\left(\mod m\right)$$ METHOD3: 平方伪随机
$$x_{n+1}\equiv x_{n}^{2}+1\left(\mod m\right)$$
- 群的定义
非空集合
$$G$$ 满足
G1: 结合律
$$\forall a,b,c\in G,\left(ab\right)c=a\left(bc\right)$$ G2: 单位元
$$\exists e\in G,\forall a\in G,ae=ea=a$$ G3: 可逆性
$$\forall a\in G,\exists a^{-1}\in G,aa^{-1}=a^{-1}a=e$$
-
Abel群/交换群
群
$$G$$ 满足-
G4: 交换律
$$\forall a,b\in G,ab=ba$$
-
G4: 交换律
-
定义和性质
-
群
$$G$$ 的元素个数叫做群$$G$$ 的阶，记作$$\left|G\right|$$ -
单位元唯一
-
逆元唯一
-
$${\left(a_1a_2\cdots a_n\right)}^{-1}=a_{n}^{-1}\cdots a_{2}^{-1}a_{1}^{-1}$$ -
$$a^{m}a^{n}=a^{m+n}$$ ，$${\left(a^m\right)}^n=a^{mn}$$ -
$$x,y\in G$$ ，$$G$$ 为Abel群，$${\left(xy\right)}^n=x^ny^n$$ -
$$\left{ \begin{array}{lr} ax=b\ ya=b \end{array} \right.$$ 在
$$G$$ 中有解，$$G$$ 满足结合律$$\Longleftrightarrow G$$ 为一个群
-
-
子群
-
定义
-
子群：$$H$$ 为
$$G$$ 的一个子集，$$H$$ 为一个群，记作$$H\leq G$$ -
平凡子群：$$H=\left{e\right}$$ 和
$$H=G$$ -
真子群：$$H$$ 不是平凡子群
-
-
性质
-
$$H\leq G\Longleftrightarrow\left{ \begin{array}{lr} H是满足G下的封闭二元运算\ G的单位元在H内\ \forall a\in H,a^{-1}\in H \end{array} \right.$$
-
$$H\leq G\Longleftrightarrow \forall a,b\in H,ab^{-1}\in H$$ -
$$H_1,H_2\leq G\Longrightarrow H_1\cap H_2\leq G$$
-
-
生成
-
$$X$$ 为$$G$$ 子集，设 $${\left{H_i\right}}{i\in I}$$ 为 $$G$$ 的包含 $$X$$ 的所有子群，则 $$\cap{i\in I}{H_i}$$ 为$$G$$ 的由$$X$$ 生成的子群，记作 $$$$-
$$X$$ 的元素为 $$$$ 生成元 -
若
$$G=<a_1,\cdots,a_n>$$ ，则$$G$$ 为有限生成的 -
若
$$G=$$ ，则$$G$$ 为$$a$$ 生成的循环群
-
-
$$G$$ 为交换群，$$X=<a_1,\cdots,a_t>$$，$$=\left{ \begin{array}{lr} \left{a_{1}^{n_1}\cdots a_{t}^{n_t}\mid a_i\in X,n_i\in Z,1\leq i\leq t\right} &G为乘法群\ \left{n_1a_{1}\cdots n_ta_{t}\mid a_i\in X,n_i\in Z,1\leq i\leq t\right} &G为加法群 \end{array} \right.$$，特别的，$$\forall a\in G,=\left{ \begin{array}{lr} \left{a^n\mid n\in Z\right} &G为乘法群\ \left{na\mid n\in Z\right} &G为加法群 \end{array} \right.$$
-
-
$$\left(Z_m,+\right)$$ 的所有子群
对
$$n\neq m$$ 且$$n\mid m$$ ，$$$$ 为子群
$$<0>=\left{0\right}$$
乘法群
$$Z_{p}^{*}$$ 的所有子群和生成元
STEP 1:
$$p-1=q_1\cdots q_s$$ ，模$$p$$ 原根为$$g$$ STEP 2:
$$$$ 生成
$$p-1$$ 阶子群
$$<g^{q_i}>$$ 生成$$\frac{p-1}{q_i}$$ 阶子群
$$<1>=\left{1\right}$$
$$Z/nZ^*$$ 的所有生成元
STEP 1: 模
$$n$$ 原根为$$g$$ STEP 2: 求所有
$$d$$ ，$$\left(d,\varphi\left(n\right)\right)=1$$STEP 3: 生成元为
$$g^d$$
-
陪集
-
定义
设
$$H$$ 为$$G$$ 的子群，$$a$$ 为$$G$$ 中的任意元，则$$aH=\left{ah\mid h\in H\right}$$ 为$$G$$ 中的左陪集，$$Ha=\left{ha\mid h\in H\right}$$ 为右陪集$$aH$$ 中的元素叫$$aH$$ 的代表元若
$$aH=Ha$$ ，则$$aH$$ 为$$G$$ 中$$H$$ 的陪集 -
定理
-
$$\forall a\in G,aH=\left{c\mid c\in G,a^{-1}c\in H\right},Ha=\left{c\mid c\in G,ca^{-1}\in H\right}$$ -
$$\forall a,b\in G,aH=bH\Longleftrightarrow b^{-1}a\in H$$ -
$$\forall a,b\in G,aH\cap bH=\varnothing\Longleftrightarrow b^{-1}a\not\in H$$ -
$$\forall a\in H,aH=H=Ha$$
-
-
群
$$\left(Z_{ha},+\right)$$ 子群 $$$$ 的所有陪集STEP 1: $$$$ 生成子群
$$\left{0,a,2a,\cdots,\left(h-1\right)a\right}$$ STEP 2: 陪集为
$$\left{m+0,m+a,m+2a,\cdots,m+\left(h-1\right)a\right},m=0,\cdots,a-1$$
-
商集
-
定义
$$G/H=\left{aH\mid a\in G\right}$$ $$G/H$$ 中左（右）陪集的个数叫做$$H$$ 在$$G$$ 中的指标，记作$$\left[G:H\right]$$ -
拉格朗日定理
$$H\leq G\Longrightarrow \left|G\right|=\left[G:H\right]\left|H\right|$$ $$K,H\leq G,K\leq H\Longrightarrow \left[G:K\right]=\left[G:H\right]\left[H:K\right]$$
-
-
正规子群
$$H\leq G,H$$ 满足$$\forall a\in G,aH=Ha$$ -
商群
$$N$$ 为$$G$$ 的正规子群，$$\left(aN\right)\left(bN\right)=\left(ab\right)N$$，$$G/N$$ 构成一个商群
$$m+$$ 在$$Z_{ka}/$$ 里的阶
写出 $$$$
$${\left(m+\right)}\cdot{\mathrm{ord}\left(m+\right)}=$$
-
定义
-
同态：$$f:G\rightarrow G^\prime,\forall a,b\in G,f\left(ab\right)=f\left(a\right)f\left(b\right)$$
-
单同态：$$f$$ 为单射
-
满同态：$$f$$ 为满射
-
同构：$$f$$ 为双射，记作
$$f:G\cong G^\prime$$ -
自同态：$$G=G^\prime$$
-
像：$$f:X\rightarrow Y,A\subseteq X,B\subseteq Y,A$$ 在
$$Y$$ 中的像$$f\left[A\right]$$ 为$$\left{f\left(a\right)\mid a\in A\right}$$ -
逆像：$$B$$ 在
$$X$$ 中的逆像$$f^{-1}{\left[B\right]}$$ 为$$\left{x\in X\mid f\left(x\right)\in B\right}$$ -
核/核子群：$$\mathrm{ker}{\left(f\right)}=f^{-1}{\left[\left{e^\prime\right}\right]}=\left{x\in G\mid f\left(x\right)=e^\prime\right}$$
-
同态映射
$$f:Z\rightarrow \left(Z_p,+\right)$$ ，$$\ker\left(f\right)=$$
-
-
像子群：$$g\left(G\right)$$
核子群即由
$$G$$ 中所有能通过$$f$$ 映射成为$$G^\prime$$ 中的单位元的元素所组成的集合像子群即
$$G$$ 中所有元素通过$$f$$ 映射后组成的集合
-
-
性质
-
$$f$$ 为$$G$$ 到$$G^\prime$$ 的同态（同构），$$g$$ 为$$G^\prime$$ 到$$G^{\prime\prime}$$ 的同态（同构）$$\Longrightarrow f\circ g$$ 为$$G$$ 到$$G^{\prime\prime}$$ 的同态（同构） -
$$f$$ 为$$G$$ 到$$G^\prime$$ 的同态-
$$f\left(e\right)=e^\prime$$ -
$$\forall a\in G,f\left(a^{-1}\right)=f^{-1}{\left(a\right)}$$ -
$$\mathrm{ker}{\left(f\right)}\leq G$$ 且$$f$$ 为单同态$$\Longleftrightarrow \mathrm{ker}{\left(f\right)}=\left{e\right}$$ -
$$H^\prime\leq G^\prime\Longrightarrow f^{-1}{\left(H^\prime\right)}\leq G$$
-
-
-
证明
$$f:G\rightarrow G^\prime$$ 同构
STEP1:
$$f$$ 为同态映射证明
$$f:G\rightarrow G^\prime,\forall a,b\in G,f\left(ab\right)=f\left(a\right)f\left(b\right)$$ STEP2:
$$\mathrm{ker}{\left(f\right)}=\left{e\right}$$ 或$$f$$ 为单射证明
$$f\left(m\right)=f\left(n\right)\Longrightarrow m=n$$ STEP3:
$$f$$ 为满射证明
$$m=f^{-1}{\left(n\right)},f\left(m\right)=n$$
-
同态分解定理
-
自然同态
$$f:G\rightarrow G^\prime$$ 同态$$\Longrightarrow \mathrm{ker}{\left(f\right)}$$ 为$$G$$ 的正规子群$$N$$ 为$$G$$ 的正规子群$$S:G\rightarrow G/H(a\rightarrow aN)$$ 是核为$$N$$ 的同态，$$S$$ 为自然同态 -
同态基本定理
$$f:G\rightarrow G^\prime$$ 同态$$\Longrightarrow \exists$$ 唯一$$G/\mathrm{ker}{\left(f\right)}\rightarrow f\left(G\right)$$ 同构$$\bar{f}:a\mathrm{ker}{\left(f\right)}\rightarrow f\left(a\right)f=i\circ \bar{f}\circ s$$ ，其中$$s$$ 为$$G\rightarrow G/\mathrm{ker}{\left(f\right)}$$ 自然同态，$$i:c\rightarrow c$$ 为$$f\left(G\right)\rightarrow G^\prime$$ 恒等同态$$s:G\rightarrow G/N$$ 同态$$\Longrightarrow \forall a\in G,f\left(a\right)=\bar{f}\circ s\left(a\right)$$
-
-
定义
若
$$\exists a\in G,G=$$ ，则$$G$$ 为循环群，$$a$$ 为$$G$$ 的生成元使等式
$$a^n=e$$ 成立的最小正整数$$n$$ 称为$$a$$ 的阶，记为$$\mathrm{ord}\left(a\right)$$ 若
$$a$$ 为$$n$$ 阶元，则$$n$$ 阶循环群$$G=\left{a^0=e,a^1,a^2,\cdots,a^{n-1}\right}$$ -
定理
-
加群
$$Z$$ 的每个子群$$H$$ 都是循环群，且$$H=<0>$$ 或$$H==mZ,m$$ 为$$H$$ 中的最小正整数 -
每一个无限循环群同构于加群
$$Z$$ ，每一个阶为$$m$$ 的有限循环群同构于加群$$Z/mZ$$ -
$$m=\mathrm{ord}\left(a\right)$$ -
$$a^k=e\Longleftrightarrow m\mid k$$ -
$$a^r\equiv a^k\Longleftrightarrow r\equiv k\left(\mod m\right)$$ -
$$\forall 1\leq d\leq m,\mathrm{ord}\left(a^d\right)=\frac{m}{\left(d,m\right)}$$
-
-
循环群的子群是循环群
-
$$G$$ 为循环群，$$G$$ 的生成元为 $$ \left{ \begin{array}{lr} a和a^{-1} &G\text{是无限的}\ a^k,\left(k,m\right)=1 &G\text{是有限的} \end{array} \right. $$ -
若
$$G$$ 为乘法群$$\left(Z_m,\cdot\right)$$ ，则生成元$$a$$ 为模$$m$$ 的原根，$$G$$ 中共有$$m-1$$ 个元素 -
若
$$G$$ 为有限交换群，则$$\exists a_1,\cdots,a_n\in G,\mathrm{ord}\left(a_{i+1}\right)\mid \mathrm{ord}\left(a_i\right),1\leq i\leq s-1,G=<a_1,\cdots,a_s>$$
-
$$n$$ 元置换
设
$$S=\left{1,\cdots,n\right},\sigma:S\rightarrow S,k\rightarrow \sigma{\left(k\right)=i_k}$$ ，表示为 $$\sigma=\left( \begin{array}{ccc} 1&2&\cdots&n-1&n\ i_1&i_2&\cdots&i_{n-1}&i_n \end{array} \right) $$
-
-
$$\sigma^{-1}=\left( \begin{array}{ccc} i_1&i_2&\cdots&i_{n-1}&i_n\ 1&2&\cdots&n-1&n \end{array} \right)$$
-
若
$$S$$ 中部分元素$$\left{i_1,\cdots,i_k\right}$$ 满足$$\sigma{\left(i_1\right)}=i_2,\sigma{\left(i_2\right)}=i_3,\cdots,\sigma{\left(i_k\right)}=i_1$$ ，则称为$$k$$ -轮变换，简称轮换，记作$$\sigma=\left(i_1,\cdots,i_k\right)$$ -
$$k=1$$ 时为恒等置换 -
$$k=2$$ 时为对换 -
$$\sigma=\left(i_1,\cdots,i_k\right),\tau=\left(j_1,\cdots,j_l\right)$$ ，若$$k+l$$ 个元素均不相同，则$$\sigma,\tau$$ 不相交 -
任意一个置换都可以表示为一些不相交轮换的乘积，且表达式唯一
-
$$k$$ -轮换可以表示为$$2$$ -轮换，$$\left(a_1\cdots,a_k\right)=\left(a_1,a_k\right)\left(a_1,a_{k-1}\right)\cdots\left(a_1,a_2\right)$$
-
-
-
置换群
$$n$$ 元置换全体组成的集合$$S_n$$ 置换的乘法构成$$n$$ 元置换群，阶为$$n!$$ 设
$$G$$ 为$$n$$ 元群，则$$G$$ 同构一个$$n$$ 元置换群
- 定义
若
$$<R,+>$$ 构成交换群，$$<R,\cdot>$$ 构成半群（$$\forall a,b,c\in R,\left(ab\right)c=a\left(bc\right)$$），$$\cdot$$ 关于$$+$$ 适合分配律（$$\forall a,b,c\in R,\left(a+b\right)c=ac+bc,a\left(b+c\right)=ab+ac$$），则$$<R,+,\cdot>$$ 为环
-
-
交换环：$$\forall a,b\in R,a\cdot b=b\cdot a$$
-
含幺环：$$\exists e=1_R,\forall a\in R,a\cdot 1_R=1_R\cdot a=a$$
-
非零元
$$a$$ 为左零因子：$$\exists b\in R,b\neq 0,ab=0$$- 零因子：$$a$$ 同时为左零因子和右零因子，$$R$$ 为零因子环
-
$$a$$ 为左逆元：$$\exists b\in R,ab=1_R$$- 逆元：$$a$$ 同时为左逆元和右逆元
-
整环：$$R$$ 为交换环、含幺环、无零因子环
-
-
性质
-
$$\forall a\in R,0a=a0=0$$ -
$$\forall a,b\in R,\left(-a\right)b=a\left(-b\right)=-ab$$ -
$$\forall a,b\in R,\left(-a\right)\left(-b\right)=ab$$ -
$$\forall n\in Z,\forall a,b\in R,\left(nab\right)=a\left(nb\right)=nab$$ -
$$\forall a_i,b_j\in R,\left(\sum_\limits{i=1}^{n}{a_i}\right)\left(\sum_\limits{j=1}^{n}{b_j}\right)=\sum_\limits{i=1}^{n}{\sum_\limits{j=1}^{n}{a_ib_j}}$$
-
-
域
整环
$$R$$ 满足$$\forall a\in R^*=R-\left{0\right},a^{-1}\in R$$ -
交换环上的整除
设
$$R$$ 为交换环，$$a,b\in R,b\neq 0$$，若$$c\in R,a=cb$$ ，则称作$$b$$ 整除$$a$$ ，记作$$b\mid a$$ ，$$a$$ 为$$b$$ 的倍元，$$b$$ 为$$a$$ 的因子-
若
$$b,c$$ 均不为单位元，则$$b$$ 是$$a$$ 的真因子 -
$$p\in R$$ ，若$$p$$ 不是单位元，且没有真因子，则$$p$$ 为不可约元/素元 -
$$a,b\in R$$ ，若$$\exists u\in R,a-ub$$ ，则$$a,b$$ 为相伴的
-
-
环的同态与同构
$$R,R^\prime$$ 为两个环，$$f:R\rightarrow R^\prime$$-
环同态
-
$$\forall a,b\in R,f\left(a+b\right)=f\left(a\right)+f\left(b\right)$$ -
$$\forall a,b\in R,f\left(ab\right)=f\left(a\right)f\left(b\right)$$
-
-
同构
$$f$$ 为满射
-
-
特征和素域
-
$$R$$ 为环，若$$\exists p_{min}\in \mathbb{Z}^*,\forall a\in R,pa=0$$ ，则$$R$$ 的特征为$$p$$ ，若不存在，则为$$0$$ $$p$$ 为素数$$\forall a,b\in R,{\left(a+b\right)}^p=a^p+b^p$$
-
设
$$p$$ 为素数，$$f\left(x\right)=a_nx^n+\cdots+a_1x+a_0$$，$${f\left(x\right)}^p\equiv f\left(x^p\right)\left(\mod p\right)$$ -
若一个域不含真子域，则其为素域
- 设
$$F$$ 为域，若$$F$$ 特征为$$0$$ ，则$$F$$ 有一个与$$Q$$ 同构的域；若$$F$$ 特征为$$p$$ ，则$$F$$ 有一个与$$F_p$$ 同构的域，$$F_p$$ 为在$$Z_p$$ 运算下的域
- 设
-
-
理想和商环
-
$$I$$ 为$$R$$ 的子环，若$$\forall r\in R,\forall a\in I,ra\in I$$ ，则$$I$$ 为$$R$$ 的左理想若同时为左理想和右理想，则为理想
-
$$\left{0\right},R$$ 均为$$R$$ 的平凡理想 -
$$P$$ 为$$R$$ 的理想，若$$P\neq R,\forall A,B,AB\in P\Longrightarrow A\in P\or B\in P$$ ，则$$P$$ 为$$R$$ 的素理想 -
$$M$$ 为$$R$$ 的理想，若$$M\neq R,\forall $$ 理想$$N,M\subset N\in R\Longrightarrow N=N\or N=R$$ ，则$$M$$ 为$$R$$ 的极大理想 -
整环
$$Z$$ 或含幺环$$R$$ 的每一个素理想都是极大理想 -
$$R$$ 为含幺交换环，$$M$$ 为$$R$$ 的理想，则$$M$$ 为极大理想或素理想$$\Longleftrightarrow R/M$$ 为域 -
若
$$R$$ 为环，$$I$$ 为$$R$$ 的理想，则$$R/I$$ 对加法运算$$\left(a+I\right)+\left(b+I\right)=\left(a+B\right)+I$$ 和乘法运算$$\left(a+I\right)\left(b+I\right)=ab+I$$ 构成一个环当
$$R$$ 为交换环或含幺环时，$$R/I$$ 也为交换环或幺环
-
-
群
$$G$$ 的正规子群$$H$$ 将$$G$$ 分为若干陪集，相似的，环$$R$$ 的理想$$I$$ 将$$R$$ 分为不相交的陪集 -
$$f:R\rightarrow R^\prime$$ 为同态$$\Longrightarrow \ker{\left(f\right)}$$ 为$$R$$ 的理想$$I$$ 为环$$R$$ 的理想$$\Longrightarrow S:R\rightarrow R/I,a\rightarrow a+I$$ 为核为$$I$$ 的同态 -
同态基本定理：
$$R$$ 为环，$$f:R\rightarrow R^\prime$$ 为同态$$\Longrightarrow \exists$$ 唯一$$R/\ker{\left(f\right)}$$ 到像子环$$f\left(R\right)$$ 同构$$\bar{f}:a+\ker{\left(f\right)}\rightarrow f\left(a\right),f=i\circ \bar{f}\circ s$$ ，其中$$s$$ 为$$R$$ 到商环$$R/\ker{\left(f\right)}$$ 的自然同态，$$i:c\rightarrow c$$ 为$$f\left(R\right)$$ 到$$R^\prime$$ 的恒等同态
-
-
定义
$$R$$ 为整环，$$x$$ 为变量，$$R$$ 上的多项式记作$$R\left[x\right]=\left{f\left(x\right)=a_nx^n+\cdots+a_1x+a_0\mid a_i\in R,0\leq i\leq n,n\in R\right}$$ 对于多项式加法和乘法，$$R\left[x\right]$$ 为整环
-
多项式整除和不可约多项式
-
$$g\left(x\right)\mid f\left(x\right)$$ ：$$\exists q\left(x\right),f\left(x\right)\mid q\left(x\right)\cdot g\left(x\right)$$ -
$$g\left(x\right),h\left(x\right)\neq 0,g\left(x\right)\mid f\left(x\right),h\left(x\right)\mid g\left(x\right)\Longrightarrow h\left(x\right)\mid f\left(x\right)$$ -
$$g\left(x\right),h\left(x\right)\neq 0,g\left(x\right)\mid f\left(x\right),h\left(x\right)\mid g\left(x\right)\Longrightarrow \forall s\left(x\right),t\left(x\right),h\left(x\right)\mid s\left(x\right)\cdot f\left(x\right)+t\left(x\right)\cdot g\left(x\right)$$ -
不可约多项式：除
$$1$$ 和$$f\left(x\right)$$ 外，$$f\left(x\right)$$ 没有其他非常数因式，否则$$f\left(x\right)$$ 为合式
-
-
设
$$f\left(x\right)$$ 是域$$K$$ 上的$$n$$ 次可约多项式，$$p\left(x\right)$$ 是$$f\left(x\right)$$ 的次数最小的非常数饮食，则$$p\left(x\right)$$ 一定是不可约多项式，且$$\deg{p}\leq \frac{1}{2}\deg{f}$$ -
设
$$f\left(x\right)$$ 是域$$K$$ 上的$$n$$ 次可约多项式，若$$\forall $$ 不可约多项式$$p\left(x\right),\deg{p}\leq \frac{1}{2}\deg{f},p\left(x\right)\not\mid f\left(x\right)$$ ，则$$f\left(x\right)$$ 为不可约多项式
-
-
多项式欧几里得除法
-
设整环
$$R$$ 上两个多项式$$f\left(x\right)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,g\left(x\right)=x^m+\cdots+b_1x+b_0$$ ，则存在$$q\left(x\right),r\left(x\right),f\left(x\right)=q\left(x\right)\cdot g\left(x\right)+r\left(x\right)$$ $$q\left(x\right)$$ 为不完全商，$$r\left(x\right)$$ 为余式-
对于
$$f\left(x\right)$$ 有$$a\in R$$ ，存在$$q\left(x\right)$$ 和常数$$c=f\left(a\right),f\left(x\right)=q\left(x\right)\left(x-a\right)+f\left(a\right)$$ -
对于
$$f\left(x\right)$$ 有$$a\in R$$ ，$$x-a\mid f\left(x\right)\Longleftrightarrow f\left(a\right)=0$$ -
$$g\left(x\right)\mid f\left(x\right)\Longleftrightarrow r\left(x\right)=0$$
-
-
最大公因式：$$f\left(x\right),g\left(x\right),d\left(x\right)\in R\left[x\right]$$
-
$$d\left(x\right)\mid f\left(x\right),d\left(x\right)\mid g\left(x\right)$$ -
$$h\left(x\right)\mid f\left(x\right),h\left(x\right)\mid g\left(x\right)\Longrightarrow h\left(x\right)\mid d\left(x\right)$$
则
$$d\left(x\right)$$ 为最大公因式，记作$$\left(f\left(x\right),g\left(x\right)\right)$$ 若
$$\left(f\left(x\right),g\left(x\right)\right)=1$$ ，则$$f\left(x\right)$$ 和$$g\left(x\right)$$ 互质 -
-
求最大公因式（广义欧几里得除法）
假设
$$\deg f<\deg g$$
$$j$$ $$r_j$$ $$r_{j+1}$$ $$q_{j+1}$$ $$r_{j+2}$$ $$0$$ $$g\left(x\right)$$ $$f\left(x\right)$$ $$g\left(x\right)/f\left(x\right)$$ $$g\left(x\right)\mod f\left(x\right)$$ $$\cdots$$ $$\cdots$$ $$\cdots$$ $$\cdots$$ $$\cdots$$ $$n$$ $$\cdots$$ $$(g\left(x\right),f\left(x\right))$$ $$\cdots$$ $$0$$
-
-
设域
$$K$$ 上两个多项式$$f\left(x\right),g\left(x\right)$$ ，则存在$$q\left(x\right),h\left(x\right)\in K\left[x\right],f\left(x\right)=q\left(x\right)\cdot g\left(x\right)+h\left(x\right),\deg{h}<\deg{g}$$ $$\left(f\left(x\right),g\left(x\right)\right)=\left(g\left(x\right),h\left(x\right)\right)$$
-
设域
$$K$$ 上两个多项式$$f\left(x\right),g\left(x\right)$$ ，$$\deg{g}\geq1,\left(f\left(x\right),g\left(x\right)\right)=r_{k}{\left(x\right)},r_{k}{\left(x\right)}$$ 为广义欧几里得除法中最后一个非零余式
-
$$s_k\left(x\right)\cdot f\left(x\right)+t_k\left(x\right)\cdot g\left(x\right)=\left(f\left(x\right),g\left(x\right)\right)$$
$$\left{\begin{array}{lr} s_{-2}\left(x\right)=1\\ s_{-1}\left(x\right)=0\\ t_{-2}\left(x\right)=0\\ t_{-1}\left(x\right)=1\\ s_j\left(x\right)=\left(-q_j\left(x\right)\right)s_{j-1}\left(x\right)+s_{j-2}\left(x\right)\\ t_j\left(x\right)=\left(-q_j\left(x\right)\right)t_{j-1}\left(x\right)+t_{j-2}\left(x\right)\end{array} \right.$$
-
多项式同余
-
给定
$$K\left[x\right]$$ 中一个首一多项式$$m\left(x\right)$$ ，若$$m\left(x\right)\mid f\left(x\right)-g\left(x\right)$$ ，则$$f\left(x\right)\equiv g\left(x\right)\left(\mod m\left(x\right)\right)$$ -
$$\forall a\left(x\right),a\left(x\right)\equiv a\left(x\right)\left(\mod m\left(x\right)\right)$$ -
$$a\left(x\right)\equiv b\left(x\right)\left(\mod m\left(x\right)\right)\Longrightarrow b\left(x\right)\equiv a\left(x\right)\left(\mod m\left(x\right)\right)$$ -
$$a\left(x\right)\equiv b\left(x\right),b\left(x\right)\equiv c\left(x\right)\left(\mod m\left(x\right)\right)\Longrightarrow a\left(x\right)\equiv c\left(x\right)\left(\mod m\left(x\right)\right)$$ -
$$a_1\left(x\right)\equiv b_1\left(x\right),a_2\left(x\right)\equiv b_2\left(x\right)\left(\mod m\left(x\right)\right)\Longrightarrow a_1\left(x\right)+a_2\left(x\right)\equiv b_1\left(x\right)+b_2\left(x\right),a_1\left(x\right)\cdot a_2\left(x\right)\equiv b_1\left(x\right)\cdot b_2\left(x\right)\left(\mod m\left(x\right)\right)$$
-
-
$$a\left(x\right)\equiv b\left(x\right)\left(\mod m\left(x\right)\right)\Longleftrightarrow a\left(x\right)=b\left(x\right)+s\left(x\right)\cdot m\left(x\right)$$ -
$$r\left(x\right)$$ 为$$f\left(x\right)$$ 模$$m\left(x\right)$$ 的最小余式 -
构造有限域：设
$$K$$ 为一个域，$$p\left(x\right)$$ 为$$K\left[x\right]$$ 中的不可约多项式，则商环$$K\left[x\right]/p\left(x\right)$$ 对于加法式和乘法式构成一个域
-
-
本原多项式
-
设
$$p$$ 为素数，$$p\left(x\right)$$ 是$$F_p\left[x\right]$$ 中的$$n$$ 次不可约多项式，则$$F_p\left[x\right]/p\left(x\right)=\left{a_{n-1}x^{n-1}+\cdots+a_1x+a_0\mid a_i\in F_p\right}$$ 记作$$F_{p^n}$$ ，这个域元素个数为$$p^n$$ -
设
$$p$$ 为素数，$$f\left(x\right)$$ 为$$f_p\left[x\right]$$ 中的$$n$$ 次多项式，则使得$$x^e\equiv1\left(\mod f\left(x\right)\right)$$ 成立的最小正整数$$e$$ 叫做$$f\left(x\right)$$ 在$$F_p$$ 上的指数，记作$$\mathrm{ord}_p\left(f\left(x\right)\right)$$ -
整数
$$d$$ 使得$$x^d\equiv1\left(\mod f\left(x\right)\right)$$ ,则$$\mathrm{ord}_p\left(f\left(x\right)\right)\mid d$$ -
$$g\left(x\right)\mid f\left(x\right)\Longrightarrow \mathrm{ord}_p\left(f\left(x\right)\right)\mid d$$ -
$$\left(f\left(x\right),g\left(x\right)\right)=1\Longrightarrow \mathrm{ord}_p\left(f\left(x\right)\cdot g\left(x\right)\right)=\left[\mathrm{ord}_p\left(f\left(x\right)\right),\mathrm{ord}_p\left(g\left(x\right)\right)\right]$$ -
$$f\left(x\right)$$ 为$$F_p\left[x\right]$$ 上的$$n$$ 次不可约多项式，则$$\mathrm{ord}_p\left(f\left(x\right)\right)\mid p^n-1$$
-
-
若
$$\mathrm{ord}_p\left(f\left(x\right)\right)=p^n-1$$ ，则称$$f\left(x\right)$$ 为$$F_p$$ 上的本原多项式 -
设
$$p$$ 为素数，$$f\left(x\right)$$ 为$$F_p\left[x\right]$$ 上的本原多项式，则$$f\left(x\right)$$ 是$$F_p\left[x\right]$$ 上的不可约多项式
-
判别本原多项式
设
$$p$$ 为素数，$$n$$ 为正整数，$$f\left(x\right)$$ 是$$F_p\left[x\right]$$ 中的$$n$$ 次多项式，若$$x^{p^n-1}\equiv 1\left(\mod f\left(x\right)\right)$$ ，对于$$p^n-1$$ 的所有不同素因数$$q_1,\cdots,q_s$$ ，$$x^{\frac{p^n-1}{q_i}}\not \equiv1\left(\mod f\left(x\right)\right),i=1,\cdots,s$$，则$$f\left(x\right)$$ 是$$n$$ 次本原多项式
-
域的扩张
-
设
$$F$$ 为一个域，如果$$K$$ 是$$F$$ 的子域，则称$$F$$ 为$$K$$ 的扩域 -
$$F$$ 为域$$K$$ 的一个扩张，将$$F$$ 看成$$K$$ 上的向量空间，若是有限维的，则称$$F$$ 为$$K$$ 的有限维扩张，$$K$$ 上向量空间$$F$$ 的维数称为扩张次数，记为$$\left[F:K\right]$$ -
设
$$R$$ 为一个整环，$$K$$ 是包含$$R$$ 的一个域，$$F$$ 是$$K$$ 的扩张-
$$F$$ 的元素$$u$$ 称为$$R$$ 上的代数数，若存在一个非零多项式$$f\in R\left[x\right]$$ 使得$$f\left(u\right)=0$$ - 如果
$$F$$ 的每个元素都是$$K$$ 上的代数数，$$F$$ 称为$$K$$ 的代数扩张
- 如果
-
$$F$$ 的元素$$u$$ 称为$$R$$ 上的超越数，若不存在任何非零多项式$$f\in R\left[x\right]$$ 使得$$f\left(u\right)=0$$ - 如果
$$F$$ 中至少有一个元素是$$K$$ 上的超越数，$$F$$ 称为$$K$$ 的超越扩张
- 如果
-
-
$$E$$ 是域$$F$$ 上的一个扩张$$F\left(\alpha\right)$$ ，$$\alpha$$ 为$$F$$ 上的代数数，则$$E=F\left(\alpha\right)$$ 上的元素$$\beta$$ 可以表示为$$\beta=b_0+b_1\alpha+\cdots+b_{n-1}\alpha^{n-1},b_i\in F$$
-
-
Galois 域
-
由素域
$$F_p$$ 的$$n$$ 次扩张构成的有限域$$F_{p^n}$$ 为一种 Galois 域 -
有限域
$$F_{p^n}$$ 上的生成元$$g$$ 称为$$F_{p^n}$$ 的本原元，$$F_{p^n}=\left{0\right}\cup $$，$$g$$ 定义的多项式叫本原多项式- 有限域
$$F_{p^n}$$ 上的乘法群$$F_{p^n}^{*}$$ 是一个循环群
- 有限域
-
-
有限域的表示
-
$$f\left(x\right)$$ 表现形式$$F_{p^n}=\left{f\left(x\right)=a_{n-1}x^{n-1}+\cdots +a_1x+a_0\in F_p\left[x\right]\right}$$ - 易于加法运算
-
$$g$$ 表现形式$$F_{p^n}=\left{0\right}\cup =\left{0,g^0=1,g,g^2,\cdots,g^{p^n-2}\right}$$ - 易于乘法运算
-
-
有限域的本原元
寻找本原元
给定有限域
$$F_{p^n}$$ ，其中$$p$$ 为素数，设$$p^n-1$$ 的所有不同素因数为$$q_1,\cdots,q_s$$ ，则$$g$$ 是$$F_{p^n}$$ 中本原元的充要条件为$$g^{\frac{p^n-1}{q_i}}\not\equiv1,i=1,\cdots,s$$ 寻找本原元：Gauss 算法
STEP1:
令
$$i=1$$ ，取$$F_q$$ 中任一非零元$$a_i$$ ，计算其阶，记为$$\mathrm{ord}\left(a_i\right)=k_i$$ STEP2:
若
$$k_i=q-1$$ ，则$$a_i$$ 为本原元，停止循环；否则转至 STEP3STEP3:
取
$$F_q$$ 中另一非零元，满足$$b$$ 不是$$a_i$$ 的整数次幂，计算其阶，记为$$\mathrm{ord}\left(b\right)=h$$ ，若$$h=q-1$$ ，则令$$a_i+1=b$$ 为一本原元，停止循环；否则转至 STEP4STEP4: 取整数
$$t,s$$ ，使得$$t\mid k_i,s\mid h,\left(t,s\right)=1,ts=\left[k_i,h\right]$$ ，令$$a_{i+1}=a_i^{\frac{k_i}{t}}b^{\frac{h}{s}}$$ ，则$$\mathrm{ord}\left(a_{i+1}\right)=k_{i+1}=ts$$ ，$$i$$ 增加$$1$$ ，转至 STEP2
$$g$$ 的幂的运算
$$g=a_nx^n+\cdots+a_1x+a_0=\left(\overline{a_n\cdots a_0}\right)$$
乘除：正常运算
加法：异或运算
graph LR
群R,+--子集-->子群R,+--生成元-->循环群
群R,+--只含单位元-->平凡群
子群R,+--陪集-->正规子群G--aNbN=abN-->商群G/N--为域-->极大理想
R,+--封闭性-->原群R,+--结合律-->半群R,+--单位元-->幺半群R,+--逆元-->群R,+--交换律-->交换群R,+
理想-->极大理想
半群R,*--分配律-->环R,+,*--子集-->子环--陪集-->理想-->素理想
环R,+,*--无零因子-->无零因子环-->整环
幺半群R,*-->含幺环-->整环--逆元-->域
整环-->多项式环
域--不含真子域-->素域Fp--n次扩张-->Galois域Fpn--乘法群-->循环群
域--子集-->子域
域-.->椭圆曲线
环R,+,*-->含幺环
半群R,*--单位元-->幺半群R,*--逆元-->群R,*--交换律-->交换群R,*-->交换环
群R,*--置换-->置换群
交换群R,+--分配律-->环R,+,*
半群R,+-->半群R,*
环R,+,*-->交换环-->整环
半群R,+--偏序-->格--全上界/全下界-->有界格--有补-->有补格-->布尔代数
格--分配律-->分配格-->布尔代数
-
Weierstrass 方程
域
$$K$$ 上的椭圆曲线$$E$$ 方程为$$E:y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$$ 其中
$$a_1,a_2,a_3,a_4\in K,\Delta\neq0$$ $$\Delta=-d_2^2d_8-8d_4^2-27d_6^3+9d_2d_4d_6$$ $$d_2=a_1^2+4a_2$$ $$d_4=2a_4+a_1a_3$$ $$d_6=a_3^2+4a_6$$ $$d_8=a_1^2a_6+4a_2a_6-a_1a_3a_4+a_2a_3^2-a_4^2$$ - 无穷远点
$$\left{0\left(\infty,\infty\right)\right}=\left{\left(x,y\right)\in L\times L:E:y^2+a_1xy+a_3y-x^3-a_2x^2-a_4x-a_6=0\right}$$
- 无穷远点
-
简化 Weierstrass 方程
$$\left(x^\prime,y^\prime\right)\rightarrow\left(\frac{x-3a_1^2-12a_2}{36},\frac{y-3a_1x}{216}-\frac{a_1^3+4a_1a_2-12a_3}{24}\right)$$ 得到
$$E:{y^\prime}^2={x^\prime}^3+a_4x^\prime+a_6$$ $$\Delta=-16\left(4a_4^3+27a_6^2\right)\neq0$$ -
椭圆曲线与群
-
$$K$$ 为$$\mathbb{R}$$ ，$$K$$ 的特征不为$$2,3$$ 时：$$y^2=x^3+a_4x+a_6$$ $$\Delta=-16\left(4a_4^3+27a_6^2\right)\neq0$$ -
$$K$$ 为$$F_p$$ ，$$p$$ 为大于$$3$$ 的素数，$$K$$ 的特征不为$$2,3$$ 时：$$y^2=x^3+a_4x+a_6\left(\mod p\right)$$ $$\Delta=-16\left(4a_4^3+27a_6^2\right)\neq0\left(\mod p\right)$$ -
$$K$$ 为$$F_{2^n}$$ ，$$K$$ 的特征为$$2$$ 时：$$y^2+xy=x^3+a_2x^2+a_6$$ $$\Delta=a_6\neq0$$ -
其解为一个二元组
$$<x,y>,x,y\in K$$ ，将此二元组描画到椭圆曲线上便为一个点，称其为解点 -
解点构成群
-
单位元：$$0\left(\infty,\infty\right)$$ 简记为
$$0$$ -
逆元：解点
$$R\left(x,y\right)=R^{-1}\left(x,-y\right)$$ ，$$0\left(\infty,\infty\right)=-0\left(\infty,\infty\right)$$ -
加法：$$kP=P+\cdots+P$$，有时记为
$$P^k$$
-
-
椭圆曲线加法
求逆运算
$$P\left(x_1,y_1\right)\neq Q\left(x_2,y_2\right)$$ ，$$P,Q$$ 不互逆$$\left{\begin{array}{lr} x_3=\lambda^2-x_1-x_2\ y_3=\lambda\left(x_1-x_3\right)-y_1\ \lambda=\left(y_2-y_1\right)/\left(x_2-x_1\right) \end{array} \right.$$
$$P\left(x_1,y_1\right)=Q\left(x_2,y_2\right)=2P\left(x_1,y_1\right)$$ $$\left{\begin{array}{lr} x_3=\lambda^2-2x_1\ y_3=\lambda\left(x_1-x_3\right)-y_1\ \lambda=\left(3x_1^2+a_4\right)/\left(2y_1\right) \end{array} \right.$$
求逆运算
$$P\left(x_1,y_1\right)\neq Q\left(x_2,y_2\right)$$ ，$$P,Q$$ 不互逆$$\left{\begin{array}{lr} x_3=\lambda^2-x_1-x_2\left(\mod p\right)\ y_3=\lambda\left(x_1-x_3\right)-y_1\left(\mod p\right)\ \lambda=\left(y_2-y_1\right)\cdot{\left(x_2-x_1\right)}^{-1}\left(\mod p\right)\end{array} \right.$$
$$P\left(x_1,y_1\right)=Q\left(x_2,y_2\right)=2P\left(x_1,y_1\right)$$ $$\left{\begin{array}{lr} x_3=\lambda^2-2x_1\left(\mod p\right)\ y_3=\lambda\left(x_1-x_3\right)-y_1\left(\mod p\right)\ \lambda=\left(3x_1^2+a_4\right)\cdot{\left(2y_1\right)}^{-1}\left(\mod p\right)\end{array} \right.$$
-
$$F_p$$ 上$$E$$ 的阶为$$#\left(E\left(F_p\right)\right)=p+1+\sum_\limits{x=0}^{p-1}{\left(\frac{x^3+a_4x+a_6}{p}\right)}$$ ，括号为勒让德符号 -
当循环群
$$E$$ 的阶$$n$$ 是足够大的素数时，这个循环群中的离散对数问题是困难的
求逆运算
$$P\left(x_1,y_1\right)\neq Q\left(x_2,y_2\right)$$ ，$$P,Q$$ 不互逆$$\left{\begin{array}{lr} x_3=\lambda^2+\lambda+x_1+x_2+a_2\ y_3=\lambda\left(x_1+x_3\right)+x_3+y_1\ \lambda=\left(y_2+y_1\right)/\left(x_2+x_1\right) \end{array} \right.$$
$$P\left(x_1,y_1\right)=Q\left(x_2,y_2\right)=2P\left(x_1,y_1\right)$$ $$\left{\begin{array}{lr} x_3=\lambda^2+\lambda+a_2\ y_3=x_1^2+\left(\lambda+1\right)x_3\ \lambda=\left(x_1^2+y_1\right)/\left(x_1\right) \end{array} \right.$$
STEP1: 密钥准备
选取素数
$$p$$ ，获取$$p$$ 的一个原根$$r$$ ，一个秘密整数$$0\leq a\leq p-1$$ STEP2: 公钥
$$\left(p,r,b\right)$$
$$b\equiv r^a\left(\mod p\right)$$ STEP3: 加密信息
$$P$$ 选取随机数
$$1\leq k\leq p-2$$
$$\gamma=r^k\left(\mod p\right)$$
$$\delta\equiv P\cdot b^k\left(\mod p\right)$$ STEP4: 解密
$$D\left(C\right)=\overline{\gamma^a}\delta$$