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

数论day2——离散对数、元根[pixiv]https://www.pixiv.net/member_illust.php?mode=medium&illust_id=608027341离散对数离散对数定义大步小步走2元根一些概念阶和元根例题1离散对数定义给定a,…

大家好,欢迎来到IT知识分享网。

这里写图片描述
[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) ,就很容易啦

嘛,就这么结束吧。(本来还有反演的,人太懒就不写了吧)

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/32165.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信