中国剩余定理
设$m_1,m_2,\dots,m_k$两两互素，则方程组：
$$ \begin{equation} \begin{cases} x\equiv a_1(\bmod\space m_1) \\ x\equiv a_2(\bmod\space m_2) \\ \dots \\ x\equiv a_k(\bmod\space m_k) \end{cases} \end{equation} $$有唯一解：$x\equiv M_1M_1^{-1}a_1+M_2M_2^{-1}a_2+\dots+M_kM_k^{-1}a_k(\bmod\space m)$
其中，$m=m_1m_2\dots m_k$，$M_i=\frac m{m_i}$，$M_iM_i^{-1}\equiv 1(\bmod\space m_i)$
RSA密码算法
密钥生成
- 选择两个保密的大素数$p$、$q$
- 取$n=p*q$，并计算$n$的欧拉函数值：$\varphi(n)=(p-1)*(q-1)$
- 选择一个介于1与$\varphi(n)$之间的整数$e$，且满足$\gcd(\varphi(n),e)=1$，即与$\varphi(n)$互素
- 计算$e^{-1}(\bmod\space\varphi(n))$得到$d$
将公钥设为$(e,n)$，私钥为$(d,n)$
加密
$$ c\equiv m^e(\bmod\space n) $$解密
$$ m\equiv c^d(\bmod\space n) $$Rabin密码算法
密钥生成
固定了$e=2$，且p、q的阶需要相同
公钥为$n$，私钥为$(p,q)$
加密
$$ c\equiv m^2(\bmod\space n) $$解密
相当于求解二次同余方程$x^2\equiv c\bmod n$，等价于求解$x^2\equiv c\bmod p$与$x^2\equiv c\bmod q$，即：
$$ \begin{equation} \begin{cases} x\equiv \sqrt c\bmod p \\ x\equiv \sqrt c\bmod q \\ x\equiv -\sqrt c\bmod p \\ x\equiv -\sqrt c\bmod q \end{cases} \end{equation} $$求解后一共会产生四组解，逐个验证并选择有意义的一项作为明文即可
当p、q之间的关系满足$p\equiv q\equiv 3\bmod4$时，整个过程可以简化
- 先使用欧几里得算法（辗转相除），求得$sp+tq=1$
- 计算$u\equiv c^{\frac{p+1}4}\bmod p$，$v\equiv c^{\frac{q+1}4}\bmod q$
- 计算$x\equiv (tqu+spv)\bmod n$，$y\equiv (tqu-spv)\bmod n$
然后就可直接得到$x^2\equiv c\bmod n$的四个根：$\begin{cases} x,\\ -x\bmod n,\\ y,\\ -y\bmod n \end{cases}$
椭圆曲线计算
Weierstrass方程为：$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$
若域F的特征不为2或3，则应用特定变换后，Weierstrass方程变为：
$$ y^2=x^3+a_4x+a_6 $$椭圆曲线上的加法原则是：P、Q为E上两点，作P、Q连线L，L会与E交于第三点-R，过-R作直线$L^\prime$，则$L^\prime$与E的交点就是$P\oplus Q$的结果
设$P_1(x_1,y_1)$在E上，则$-P_1=(x_1,-y_1-a_1x_1-a_3)$
E对于运算法则**$\oplus$构成一个交换群**
设E上两点$\text P_1(\text x_1,\text y_1)$ 、$\text P_2(\text x_2,\text y_2)$，则首先有$-\text P_1(\text x_1,-\text y_1)$，然后，有：
$$ \begin{equation} \begin{cases} x_3=\lambda ^2-x_1-x_2 \\ \\ y_3=\lambda (x_1-x_3)-y_1 \end{cases} \end{equation} $$$$ \begin{equation} \lambda =\begin{cases} \frac{y_2-y_1}{x_2-x_1},\space P_1\neq P_2 \\ \\ \frac{3x_1^2+a_4}{2y_1},\space P_1 =P_2 \end{cases} \end{equation} $$如此可进行k倍点运算，本质上就是不断相加，在椭圆曲线中的k倍就可以类比于实数中的k次方运算
多项式计算
环R上的不定元$x$的多项式全体：$R[x]=\{f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0\space|\space a_i\in R,n\in N\}$，即所有系数都取自环R中
以下所有计算都是在$\text{GF}(2^8)$域上进行的，在进行表示时，参考：$37=100101=x^5+x^2+1$
多项式相加
直接进行按位异或即可，需要注意在$\text{GF}(2^8)$中2 = 0，多项式相加的例子如下：
$$ \begin{split} 37+28&=100101+11100\\ &=(x^5+x^2+1)+(x^4+x^3+x^2)\\ &=x^5+x^4+x^3+1 \end{split} $$多项式模乘
有两个方法：
套公式
首先有公式：$x^8\bmod m(x) = [m(x) – x^8] = x^4 + x^3 +x +1$，其中$m(x)$多取$x^8+x^4+x^3+x+1$
然后对于$f(x)=(b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x)\operatorname{mod}m(x)$，若$b_7=1$，则说明需要取模计算，因为达到了8次方，此时直接使用以上公式，将$x^8$换为$x^4 + x^3 +x +1$，得到：$f(x)=(b_{6}x^{7}+b_{5}x^{6}+b_{4}x^{5}+b_{3}x^{4}+b_{2}x^{3}+b_{1}x^{2}+b_{0}x)+(x^{4}+x^{3}+x+1)$
对于更高次的如$x^9$，可以直接视为$x^8*x=x^5+x^4+x^2+x$，直到$x^{12}=x^8+x^7+x^5+x^4$，将$x^8$替换为$x^4+x^3+x+1$即可，故$x^{12}=x^7+x^5+x^3+x+1$，以此类推更高次幂的情况
正常取模计算
- 直接将两个运算数字表示为多项式形式
- 按照正常的多项式乘法法则进行乘法操作，得到一个高次的多项式（仍然注意1+1=0这个特点）
- 使用多项式除法的方式直接计算取模结果
多项式求逆元
使用扩展的欧几里得算法即可，例如记$f(x)=x^4+x^2+x$；$g(x)=x^7+x^5+x^2+1$，求$f^{-1}(x)\bmod g(x)$：
$$ \begin{split} x^7+x^5+x^2+1 &= (x^3+1)(x^4+x^2+x)+(x+1)\\ x^4+x^2+x &= (x^3+x^2+1)(x+1)+1 \end{split} $$$$ \begin{split} 1 &= x^4+x^2+x-(x^3+x^2+1)(x+1)\\ &= f-(x^3+x^2+1)[g-(x^3+1)f]\\ &= (x^6+x^5+x^2)f-(x^3+x^2+1)g \end{split} $$于是得到：$\begin{cases} f^{-1}(x)\bmod g(x)=x^6+x^5+x^2\\ g^{-1}(x)\bmod f(x)=x^3+x^2+1 \end{cases}$