数论day2——离散对数、元根

[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=60802734

1 离散对数
离散对数定义
大步小步走
2 元根
一些概念
阶和元根
例题

1离散对数

定义

给定a,b,m，其中a与m互素，求最小的非负（正）整数x，使得：
a^x≡b (mod m)
我们称x为模m意义下，以a为底的b的离散对数，记作ind a b。

那么，给出a,b,m，（假设a与m互素）如何求x？

大步小步走

这有一个技巧：显然，任何数x都可以分解为 x=i*c+j（i，j为正整数，c为某固定数）

我们先在[2,m-1]内选一个数c，计算出：a^0,a^1,a^2,a^3,……,a^c-1
如果发现其中某个值是b，就找到答案了

如果没有，我们将已计算出的值放入数据结构中（平衡二叉树（map），哈希表都可以），以便快速通过a^i的值得到i。然后再依次计算出：
b*a^-c, b*a^-2c, … , b*a^-kc

每算完一个b*a^-c，我们就看数据结构中是否有一个值a^j等于它，如果有，那么它们满足：
a^j≡b*a^-ic (mod m)
易证等价于：
a^(ic+j)≡b (mod m)

分析复杂度：如果我们上面用哈希表存，那么可以o(1)判断某个值是否存在。
那么我们总共需要计算的个数是o(b+m/b)，我们取b=√m，可以得到o(√m)的复杂度。

注意：上面的方法不限于整数，还可以是矩阵，但都要求a存在逆元。

意义

想想平时数学课上的log，我们是怎么灵活运用的？
ind可以看做是模意义下的log。在一些换底的运用中还是很重要的。

2元根

一些概念

剩余系：
对于给定模数m（m>0），如果有一组数{ai}：a1,a2,a3,…,am 对于任何数a，存在唯一数ai满足：a≡ai (mod m) ，那么我们将{ai}称作模m的一组完全剩余系
（好吧，这是学长讲稿上的定义，我仍然理解不了。。。）

既约剩余系：对于给定模数m（m>0），如果有一组数{ai}：a1,a2,a3,…,ak 满足：gcd（ai，m）=1且对于任何和m互质的数a，有唯一的ai满足：a≡ai（mod m） 那么我们将{ai}称作模m的一组既约剩余系，也叫做缩系。
容易看出，这概念像极了欧拉函数。模m的既约剩余系的个数记作φ（m）

阶和元根

阶：
给定一个与m互素的a，则最小的一个满足：a^r≡1 (mod m) 的正整数r叫做a模m的阶，一般记作 r=δm(a)
显然，r可以用离散对数求出。

元根：
对于模数m，如果存在一个数g，满足：δm(g)=φ（m） 我们则称g为模m的一个元根

那么元根有什么用呢?
我们先从定义的本质去理解一下：
1、阶是什么？“最小的r“，再大一点，a^r模m的值就会出现循环，直到a^2r≡1(mod m)
一组数据模拟一下：7^r（mod 9)
r : 1 2 3 4 5 6 7
ans:7 4 1 7 4 1 7
由此可见，r=3是阶，而过了之后就是循环
2、元根相对于阶有什么特殊的地方？ g^φ(m)≡1 (mod m) 结合上面的结论，即φ(m)次方后就是循环，即g^r≡a (mod m)的a有φ(m)个不同的。因为g与m是互质的，所以所有的”a”都与m互质。我们发现这一组不同的”a”就是m的缩系。

在明白了上面两点后，我们就发现了元根的作用了：
对于任意一个缩系中的元素，都与一个g^i这种形式对应起来。假如我们找到了一个模m的元根g，想求其缩系中的某元素a对应的指数是什么，我们就可以用离散对数找到满足：g^i≡a (mod m) 的i。（还理解不清楚的，后面的例题可能会有些帮助）（讲道理我也没太清楚，题做少了。。。）

那么怎么求元根呢？
先明确几点：
1、不是所有数都有元根。只有形如: 1，2，4，p^a，2p^a 的数存在元根(其中 a>=1 且p 是奇素数).
2、在109 范围内的所有素数的最小的元根都很小(最大的不过一百多)
然后就可以暴力枚举，判断是否是元根

如何判断呢？
如果存在正数a,b,m, 且gcd(a,m) = 1, 满足
a^b≡1 (mod m)
那么有: δm(a) | b

通过上面这个定理可以证明:
对于给定的与m>=2 互素的一个数g, g 是m 的一个元根当且仅当对于φ(m) 的所有素因子pi , 有:g^(φ(m)/pi)≡/(不同余)1 (mod m)
复杂度小于o（log）

例题

例1

给你a,b,m, 都是正整数, 其中m 是素数, 求:
a^x≡b (mod m)
其中:2<=m<=2*10^9,1<=a,b < m

很容易离散对数就可以秒了对不对

例2

给你a1,b1,a2,b2,m, 都是正整数, 其中m 是素数, 求满足下面条件的x:
ai^x≡bi (mod m) (i =1,2)
其中:2<=m<=2*10^9 且1<=ai,bi < m.

先找到m 的一个元根, 然后找到ai 和bi 的离散对数:
g^ci≡ai (mod m)
g^di≡bi (mod m)
然后就把问题化简成了:
g^(x*ci)≡g^di (mod m)
因为g 是模m 的元根, 所以上面的方程等价于:
x*ci≡di (mod m-1)
从而把问题转化为解一元一次同余方程组的问题.

例3

给你三个正整数a,b,m, 其中m 是质数, 求x 满足:
x^a≡b (mod m)
其中:1<=x,b < m

找到元根进行替换： g^(x*a)≡g^b (mod m)，就可以转化为 x*a≡b(mod m-1) ，就很容易啦

嘛，就这么结束吧。（本来还有反演的，人太懒就不写了吧）