求解模奇质数意义下的二次同余方程

2019-04-13 12:37发布生成海报

站内文章 / 模拟电子

10514 0

若有方程：

x2≡a(modp) 这个方程的解已经可以在优秀的时间内求解，不过这里只探讨

p为奇质数的情况。

O(n√)解法

首先有欧拉准则：

x2≡a(modp)有解

⇔

ap−12≡1(modp)

证明：
1.充分性。
ap−12=(x2)p−12=xp−1
由费马小定理，xp−1≡1(modp)
2.必要性。
设g为模p意义下的原根，gi≡a(modp)。
有gi(p−1)2≡1(modp)
g为原根，那么(p−1)|(i(p−1)2)
此时i为偶数，令x=gi2可以构造出一组解。

显然

BSGS可以构造出一组解，问题可以在

O(n√)内解决，不过还有更加优美的解法。

若

x2≡w(modp)无解，则称

w为

p的一个二次非剩余系中的一类。对于这样的

w，有：

wp−12≡−1(modp)

证明：
由费马小定理:wp−1≡1(modp)
⇒wp−12≡±1(modp)
由欧拉准则有:wp−12≢1(modp)
得证：wp−12≡−