离散对数概念

周海汉 2018-06-27
2018-06-27

概念

同余运算

数学上,同余(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 $则

在数论中,对正整数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的结果一定互不相同。

性质

  1. $a^x \equiv a^y \pmod m$ => $ x \equiv y \pmod {δ_m(a)}$

  2. 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)$时的离散对数值.

性质

离散对数和一般的对数有着相类似的性质:

示例

对模5,$\phi(5)=5-1=4$.有个原根是2. 因为

参考

维基 离散对数


如非注明转载, 均为原创. 本站遵循知识共享CC协议,转载请注明来源