离散对数和原根

我超,⚪!

因为看不懂网上的离散对数，所以来写篇blog梳理一下(

前置知识: 大概无？

首先,让我们复习一下群论知识.

群G的阶就是其元素的个数,记作ord(G)或|G|,群内元素a的阶是使得 $a^m=e$ 成立的最小正整数m,记作ord(a)或|a|

循环群:记为 $G_{n}$ ,群G中任意一个元素 $a=g^{k}$ ,其中k为整数,g为群G的生成元,而生成元的阶就是群G的阶.显然单位元 $e=g^{0}$ .设 $g^x=e$ ,由于任意一个元素都可由g生成,所以x>=n(若xn,则1~n之间一定存在两个数i,j,满足 $g^i=g^j$ ,所以 $g^(j-i)=e$ ,则与x>n相悖.

综上,生成元的阶即为群的阶, $g^n=g^0=e$ .而阶为n的有限循环群同构于模n剩余类对于加法构的群 $Z_{n}$ .

循环群中,设a的阶最大为p,则p是其他所有元素的阶的倍数(证明:假设存在元素b,其阶r小于p,且r不是p的因数,设 $r=q^{k_{r} }*j$ , $p=q^{k_{p} }*i$ ,则 $a^{q^{k_{p} } }$ 的阶数为i, $b^{j}$ 的阶数为 $q^{k_{r} }$ ,二者相乘,能造出一个阶数更大的数,与前提相悖)

再来复习一下同余方程.

对于任意的a,至多有n个不同的x<m满足nx=a mod m

假设,存在n+1个不同的x满足nx=a mod m,那么对于方程 $nx-n*{x_{n+1} }=0 mod m$ 也存在n+1个不同的解(二者等效)

设gcd(m,n)=d,m=kd,n=jd那么上述第二个方程可化为, $j(x-{x_{n+1} })=0 mod k$ ,其中j,k互质,所以存在逆元,故所有的x在mod k意义下和 $x_{n+1}$ 相等,即 $x=x_{n+1}+p*k$ ,又由于x 在mod m下不同,则最多有d-1个不同的p,所以解的个数小于d-1,即小于n.

综上,最多有n个不同的x<m满足nx=a mod m

上述问题还有一个朴素的证法:nx= a mod m,假设存在n+1个解,易知将解重新排序后,设解之间的差为dif,则dif*n=lcm(n,m),即nx增加了lcm(n,m),则最后一个解-第一个解=dif*n,则x实际上增加了lcm(n,m),所以第一个解和最后一个解 mod m意义上相同,故不存在超过n个解

事实上,会了这个证明可以看看https://codeforces.com/gym/104090/problem/A

该题实际上就利用了nx+my中,y的有效值不会超过n个,遍历一遍sum+nx+my的结果最终取最小值.

最后再复习一下拉格朗日定理.

综合一下上述知识,首先,我们能推出

G是循环群
对于任意任意一个元素a,最多有n个不同的元素x满足$x^n$=a

这两个条件是互相等价的(上推下等价于xn=a mod m 最多有n个不同解,在前文中已解决)(因为所有元素的阶中,最大的阶,是其他元素阶的倍数,所以存在一个数满足所有的数的d次方都为e,因为最多有d个元素满足该条件,所以d=n,下推上成立)

综上,对于质数p,mod p所生成的剩余系,对于乘法构成了一个循环群

阶:已知,当gcd(a,m)=1时,一定存在一个最小的数t,满足a^t=1 mod m(因为m的欧拉函数值满足这个条件,所以t<=m的欧拉函数值)

懒得写公式了,抄抄oiwiki ==

关于阶,一些很显然的性质:

原根的一些性质:

原根个数:若一个数m有原根,则原根个数为m的欧拉函数值的欧拉函数值(即嵌套两层欧拉函数)(证明:设m有原根g,求g^k的阶,易得k与m的欧拉函数值互质时,其阶为m的欧拉函数值)
原根存在定理:一个数m存在原根当前仅当m=2,4,p^a,2*p^a(证明:先证p,与循环群类似,存在一个元素的阶是其他所有元素的阶的倍数,由拉格朗日定理和费马小定理得,该元素即为原根)
若m存在原根,则最小原根是不大于m^(1/4)的(所以我们可以暴力找原根)

对数将乘法运算映射到加法运算上,若在mod n意义下存在原根p,则我们可以构建对数运算

了解一下多值函数的意义