对于二次剩余式 $$x^2\equiv n\pmod p$$
其中$p$为奇素数，且$p \nmid n$，求$x$。
Cipolla算法#
$Cipolla$和之前就写过的三次剩余是同一个思路，所以我在写完$Cipolla$后感觉好像什么都没变。
构造一个环
$$R=\frac{\mathbb{Z}_p[x]}{x^2-a}=\set{\alpha+\beta Y | \alpha,\beta,\in\mathbb{Z}_p,Y^2=a}$$
可知，
对于$z\in R$，即$z=\alpha+\beta Y$，有$z^{p-1}\equiv 1\pmod{p}$
如果$z^{\frac{p-1}{2}}=\beta_0 Y$，则有$(\beta_0 Y)^2\equiv\beta_0^2a\equiv1\pmod{p}$，即$\sqrt{a}\equiv\beta_0^{-1}\pmod{p}$
代码实现#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| mt19937 rng(__builtin_ia32_rdtsc());
inline ll randint(ll l, ll r) {
return uniform_int_distribution<ll>(l, r)(rng);
}
ll qpow(ll x, ll n, ll mod) {
ll res = 1LL;
for (x %= mod; n > 0LL; n >>= 1, x = x * x % mod) {
if (n & 1LL) res = res * x % mod;
}
return (res + mod) % mod;
}
struct R {
ll a, p, x, y;
R(ll _a, ll _p) : a(_a), p(_p) { x = 1LL, y = 0LL; }
void rand() {
x = randint(0, p - 1);
y = randint(0, p - 1);
}
R &operator*=(const R &rhs) {
ll _x = (x * rhs.x + y * rhs.y % p * a) % p;
ll _y = (x * rhs.y + y * rhs.x) % p;
x = _x, y = _y;
return *this;
}
void pow(ll n) {
R res(a, p), b = *this;
for (; n; n >>= 1, b *= b) {
if (n & 1LL) res *= b;
}
x = res.x, y = res.y;
}
};
ll Cipolla(ll a, ll p) {
a = (a % p + p) % p;
if (a == 0) return 0LL;
if (qpow(a, (p - 1) / 2, p) != 1LL) return -1LL;
// No Solution
if (p % 4 == 3) return qpow(a, (p + 1) / 4, p);
R t(a, p);
while (true) {
t.rand(), t.pow((p - 1) / 2);
if (t.x == 0 && t.y != 0) {
return qpow(t.y, p - 2, p);
}
}
assert(false);
return -1;
}
|
Tonelli-Shanks算法#
(来自柯召的《初等数论》)
由于$n^{\frac{p-1}{2}}\equiv 1\pmod p$，得到$(\pm n^{\frac{p+1}{4}})^2\equiv n\pmod p$。
先求$n=-1$的解。
由威尔逊定理有$-1\equiv (p-1)! \pmod p$，对于右侧有：
$$1\times2\times\cdots\times(\frac{p-1}{2})\times(p-\frac{p-1}{2})\times\cdots\times(p-1)\equiv\left((\frac{p-1}{2})!\right)^2\pmod p$$
$4\mid (p-1)$，所以负号没了。
同样的，由于$n^{\frac{p-1}{2}}\equiv 1\pmod p$，我们得到
$n$适合$n^{\frac{p-1}{4}}\equiv 1\pmod p$或$n^{\frac{p-1}{4}}\equiv-1\pmod p$
- $n^{\frac{p-1}{4}}\equiv 1\pmod p$，有$(n^{\frac{p+3}{8}})^2\equiv n\pmod p$
- $n^{\frac{p-1}{4}}\equiv-1\pmod p$，有$((\frac{p-1}{2})!\times n^{\frac{p+3}{8}})^2\equiv n\pmod p$
设$p\equiv 1\pmod 8,(\frac{n}{p})=1,(\frac{N}{p})=-1$，则同余式有解
$$\pm n^{\frac{h+1}{2}}N^{s_k}$$
其中$p=2^kh+1,2\nmid h,s_k\geq0$是某个整数。
证明：设$p=2^kh+1,k\geq3,2\nmid h$。
由于$(\frac{n}{p})=1, (\frac{N}{p})=-1$，我们得出
$$n^{2^{k-1}h}\equiv 1\pmod p$$
$$N^{2^{k-1}h}\equiv-1\pmod p$$
因此下面的两个同余式有且只有一个成立
$$n^{2^{k-2}h}\equiv 1\pmod p$$
$$n^{2^{k-2}h}\equiv-1\pmod p$$
故有非负整数$s_2=hf$（$f=0$或$1$）使
$$n^{2^{k-2}h}\times N^{2^{k-1}s_2}\equiv1\pmod p$$
成立。
于是下面两个同余式有且只有一个成立
$$n^{2^{k-3}h}\times N^{2^{k-2}s_2}\equiv 1\pmod p$$
$$n^{2^{k-3}h}\times N^{2^{k-2}s_2}\equiv-1\pmod p$$
故又有非负的$s_3=s_2+2hf_1$（$f_1=0$或$1$）满足下式
$$n^{2^{k-3}h}\times N^{2^{k-2}s_3}\equiv1\pmod p$$
因为$k$是有限整数，故必有一非负的$s_k$使得
$$n^h\times N^{2s_k}\equiv1\pmod p$$
故
$$n^{h+1}N^{2s_k}\equiv n\pmod p$$
即
$$\left(n^{\frac{h+1}{2}}N^{s_k}\right)^2\equiv n\pmod p$$
代码实现#
时间复杂度，平均$\mathcal{O}(\log p)$，最坏$\mathcal{O}(\log^2 p)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| ll qpow(ll x, ll n, ll mod) {
ll res = 1LL;
for (x %= mod; n > 0LL; n >>= 1, x = x * x % mod) {
if (n & 1LL) res = res * x % mod;
}
return (res + mod) % mod;
}
ll Tonelli_Shanks(ll a, ll p) {
a = (a % p + p) % p;
if (a == 0) return 0LL;
if (qpow(a, (p - 1) / 2, p) != 1LL) return -1LL;
// No Solution
if (p % 4 == 3) return qpow(a, (p + 1) / 4, p);
ll k = __builtin_ctzll(p - 1), h = p >> k, N = 2;
// p = 1 + h * 2^k
while (qpow(N, (p - 1) / 2, p) == 1) N++;
// find a non-square mod p
ll x = qpow(a, (h + 1) / 2, p);
ll g = qpow(N, h, p);
ll b = qpow(a, h, p);
for (ll m = 0; ; k = m) {
ll t = b;
for (m = 0; m < k && t != 1LL; m++) {
t = t * t % p;
}
if (m == 0) return x;
ll gs = qpow(g, 1 << (k - m - 1), p);
g = gs * gs % p;
b = b * g % p;
x = x * gs % p;
}
assert(false);
return -1;
}
|