二次剩余
勒让德符号（Wikipedia）
\[{\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{if }}a{\text{ is a non-quadratic residue modulo }}p,\\0&{\text{if }}a\equiv 0{\pmod {p}}.\end{cases}}}\]
定理0
在模\(p\)意义下，分别有\(\frac{p-1}{2}\)个二次剩余和非二次剩余。
定理1
\[\left({\frac {a}{p}}\right) \equiv a^{\frac{p-1}2}\pmod p\]
（仿定理0）
Cipolla 算法
- 假设要求\(x^2\equiv n\pmod p\)，随机一个数\(a\)，使得\(a^2-n\)为非二次剩余。
- 设\(w=\sqrt{a^2-n}\)，构造一个所有数都可以表示成\(a+bw\)的域\(\mathbb F_{p^2}\)（？）。
- 则一个可行的\(x\equiv(a+w)^{\frac{p+1}2}\pmod p\)。快速幂即可求。
定理2
\[w^p=-w\pmod p\]
定理3
\[\forall x, y\in \mathbb F_{p^2}:(x+y)^p\equiv x^p+y^p\pmod p\]
定理4
\[(a+w)^{p+1}\equiv n\pmod p\]
代码
#include <bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
int t, n, p, a, w;
ostream& operator <<(ostream &, struct p2);
struct p2{
ll a, b;
p2 operator *(const p2 &q) {
return (p2){(a*q.a+b*q.b%p*w)%p, (a*q.b+b*q.a)%p};
}
p2 operator %(const int p) {
return (p2){a%p, b%p};
}
};
template<typename T>
T qpow(T a, int x, T e) {
return (x?(qpow(a*a%p, x/2, e)*(x&1?a:e)):e)%p;
}
signed main() {
cin >> t;
while (t--) {
cin >> n >> p;
int tmp = qpow<ll>(n, (p-1)/2, 1);
if (tmp == 0) {
cout << 0 << endl;
continue;
} else if (tmp == p-1) {
cout << "Hola!\n";
continue;
}
do {
a = rand()%p;
} while (qpow<ll>(w=((ll)a*a+p-n)%p, (p-1)/2, 1) != p-1);
p2 x = qpow((p2){a/*注意这里的a……调了半天*/, 1}, (p+1)/2, (p2){1,0});
cout << min(p-x.a, x.a) << ' ' << max(p-x.a, x.a) << endl;
}
}