数论

第一章 整除、公因数公倍数 若$a\mid b$，则$\exist c$，使得$b=ac$ 若$p\mid ab$，则$p\mid a$或$p \mid b$ 若$a \mid mb$且$(a,b)=1$，则$a \mid m$ （单边消去） $am \mid bm ,\space m \ne 0\Leftrightarrow a \mid b$ （双边消去） $[a,b](a,b)=ab$ $d =(a,b)$，则$(\frac ad,\frac bd)=1$ a，b的最大公因数可以用辗转相除法求，例如$(78,108)=(78,30)=(18,30)=(18,12)=(6,12)=6$ 第二章 同余关系 $a\equiv b\mod m \Leftrightarrow m \mid a-b$ （证明mx+mx通过mm的完系时常用） 对于同余式组： $$ \begin{cases} a\equiv b\mod m\\ \alpha \equiv \beta \mod m \end{cases} $$有$a+\alpha \equiv b+\beta \mod m$；$a\cdot\alpha \equiv b \cdot\beta \mod m$；$f(a) \equiv f(b)\mod m$ 威尔逊定理：$(p-1)!+1 \equiv 0\mod p$ ...

中国剩余定理 设$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} $$求解后一共会产生四组解，逐个验证并选择有意义的一项作为明文即可 ...