高次同余方程

2020-08-04 本文已影响0人 dachengquan

高次同余方程有 $a^x \equiv b \pmod p$ 和 $x^a \equiv b\pmod p$ ,我们目的就是求出x。首先看前者。
问题：给定整数a，b，p，其中a，p互质，求一个非负整数x，使得 $a^x \equiv b \pmod p$ 。
Baby Step,Giant Step算法
设 $x = i*t+j$ ,其中 $t=\lceil \sqrt p\rceil$ , $1\leq j\leq t-1$ ,则方程变为 $a^{i*t}\equiv b*a^j \pmod p$ ,将 $b*a^j \pmod p$ 插入hash表中。枚举i的所有取值，查询hash表中有无对应的 $b*a^j \pmod p$ 。时间复杂度 $O(\sqrt p)$ 。

高次同余方程

猜你喜欢

热点阅读