概念
同余运算
数学上，同余（congruence modulo，符号：$\equiv$）是数论中的一种等价关系。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余是抽象代数中的同余关系的原型。最先引用同余的概念与“$\equiv$”符号者为德国数学家高斯。
两个整数 a， b，若它们除以正整数 m所得的余数相等，则称 a， b对于模 m同余
记作 $ a\equiv b{\pmod {m}}$
读作 a同余于b 模m，或读作 a与 b关于模 m同余。
比如 $ 26\equiv 14{\pmod {12}} $。
同余类(congruence class)
如同任何同余关系，对于模 n同余是一种等价关系，整数 a的等价类是一个集合 $ {\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots } $，标记为 $ {\overline {a}}_n $。由对于模 n同余的所有整数组成的这个集合称为同余类（congruence class或residue class）；假若从上下文知道模 n，则也可标记为 [a]。
同余类中的每个元素都可以拿来代表该同余类，称为该同余类的代表数（英语：representative）
余数系统
余数系统（英语：residue system）亦即模 n同余类的代表数的集合，通常使用的代表数是最小非负整数，因为它是除法中的应当余数。 一个完整余数系统（英语：complete residue system）指的是模n的全部同余类的代表数的集合；因为余数系统中的任二元素不同余于模 n，所以它也称为非同余余数的完整系统（英语：complete system of incongruent residues）。例如，模3有三个同余类[0],[1],[2]，其完整余数系统可以是 {9,12+1,15+2} 如果该集合是由每个同余类的最小非负整数所组成，亦即 {0,1,2,…,n-1}，则称该集合为模n的最小余数系统（英语：least residue system）。
模 n完整余数系统中，与模n互质的代表数所构成的集合，称为模n的简约余数系统（英语：reduced residue system），其元素个数记为 $\phi(n)$，亦即欧拉函数。例如，模 6的简约余数系统为{1,5}或 {7,11}。如果模 n是质数，那么它的最小简约余数系统是{1,2,…,n-1}，只比最小余数系统少一个 0。
欧拉函数
欧拉定理： n，a为正整数，且n，a互质，$ n\geq 2 $则
\[a^{\phi n} \equiv 1\pmod n\]在数论中，对正整数n，欧拉函数 $ \phi (n)$是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名） 例如 $ \phi (8)=4$，因为1,3,5,7均和8互质。
欧拉函数实际上是模n的同余类所构成的乘法群（即环 ${\mathbb {Z}}/n{\mathbb {Z}}$的所有单位元组成的乘法群）的阶。
1736年，欧拉证明了费马小定理：
假若 p 为质数， a 为任意正整数，那么 $ a^{p}-a$ 可被 p 整除。
然后欧拉予以一般化：
假若 a 与 n 互质，那么 $ {\displaystyle a^{\varphi (n)}-1}$ 可被 n 整除。亦即， $ a^{\varphi (n)}\equiv 1{\pmod n}$。 其中 $\varphi (n) $即为欧拉总计函数。
如果 n 为质数，那么$ {\displaystyle \varphi (n)=n-1}$，因此，有高斯的版本：
假若 p 为质数， a 与 p 互质（ a 不是 p 的倍数），那么 $a^\equiv 1{\pmod p}$。
$\varphi (1)=1 $（小于等于1的正整数中唯一和1互质的数就是1本身）。
若n是质数p的k次幂， $ \varphi (n)=\varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1} $，因为除了p的倍数外，其他数都跟n互质。
欧拉函数是积性函数，即是说若m,n互质， $ \varphi (mn)=\varphi (m)\varphi (n)$。
阶
群元素的个数称为群的阶。
对欧拉函数，设m > 1 且 (a, m) = 1, 则使得 $a^d\equiv 1\pmod m$ 成立的最小的正整数d,称为a对模m的阶, 记为$δ_m(a)$。
如果m为质数，则 $δ_m(a)=m-1$。即群$a^{m-1}\equiv 1\pmod m$的阶为m-1
原根
对于两个正整数a和m互质，其最大公约数为1，即gcd(a,m)=1，简写为(a,m)=1. 满足 $a^d \equiv 1 \pmod m$ 的最小的 d，称为a对m的阶,记为 $δ_m(a)$，若$δ_m(a) =\varphi (m)$，则称a是模 m的原根。
由欧拉定理可知，存在正整数 d ≤ m-1，使得 $a^d\equiv 1 \pmod m$。 欧拉函数 $\varphi (m)$，即小于等于 m的正整数中与 m互质的正整数的个数，设为d。d最大值为m-1, 如果m为质数。 定义 a对模m的指数 $δ_m(a)$为使 $a^d\equiv 1 \pmod m$ 成立的最小的正整数 d。由前知 $δ_m(a)$ 一定小于等于 $ \varphi (m)$。当$δ_m(a) =\varphi (m)$，则称a是模 m的原根。
另一种定义，对(a,m)=1，即a，m互质. 如果a是m的原根，那么$a^i \pmod m$的结果两两不同,且有 $1 < a < m, 1 < i < m$. 即，$a^i \pmod m \ne a^j \pmod m$ （m为质数），其中$i\ne j$且i, j介于1至(m-1)之间，则a为m的原根。
简单的来说，如a是m的原根，那么a的1…(m-1）次幂mod m的结果一定互不相同。
性质
-
$a^x \equiv a^y \pmod m$ => $ x \equiv y \pmod {δ_m(a)}$
-
m(若存在原根)的原根数目为 ϕ(ϕ(m)) .
求解方式：
从2开始枚举，然后暴力判断$a^{m-1} \equiv 1 \pmod m$是否当且当指数为m-1的时候成立 而由于原根一般都不大，所以可以暴力得到.
例如： 设m= 7，则φ（7）等于6。φ（7）表示7的欧拉函数。 设a= 2，由于$2^3=8\equiv 1\pmod 7$，而3<6，所以 2 不是模 7 的一个原根。 设a= 3，由于$3^1\equiv 3 \pmod 7, 3^2\equiv 2 \pmod 7,3^3\equiv 6 \pmod 7,3^4\equiv 4 \pmod 7,3^5\equiv 5 \pmod 7,3^6\equiv 1 \pmod 7$，所以 3 是模 7 的一个原根。
离散对数
离散对数（Discrete logarithm）是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 $ x=\log_b a $ 是指对于给定的 a 和 b，有一个数 x，使得$b^x = a$。相同地在任何群 G中可为所有整数 k定义一个幂数为 $b^k$，而离散对数 $ \log_b a $是指使得 $b^k \equiv a \pmod m$ 整数 k。记为$k=Ind_b a$
离散对数在一些特殊情况下可以快速计算。然而，通常没有具非常效率的方法来计算它们。公钥密码学中几个重要算法的基础，是假设寻找离散对数的问题解，在仔细选择过的群中，并不存在有效率的求解算法。
定义
当模 m有原根时，设 a为模 m的一个原根，则当$ a^{k}\equiv x{\pmod {m}}$时： $ Ind_x\equiv k{\pmod {\phi (m)}}$，此处的 $ Ind_x$为 x以整数 a为底，模 $\phi (m)$时的离散对数值.
性质
离散对数和一般的对数有着相类似的性质：
\[Ind_xy\equiv Ind_x+Ind_y{\pmod {\phi (m)}} Ind_x^{y}\equiv yInd_x{\pmod {\phi (m)}}\]示例
对模5，$\phi(5)=5-1=4$.有个原根是2. 因为
\[2^0\equiv 1,2^1\equiv 2,2^2\equiv 4,2^3\equiv3 \pmod 5 Ind_2 1=0,Ind_2 2=1,Ind_2 4=2,Ind_2 3=3\]参考
如非注明转载, 均为原创. 本站遵循知识共享CC协议,转载请注明来源
