1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
ll sqrtMod(ll a, ll p) {
assert(powMod(a, (p + 1)/2, p) == 1); //a ist ein quadrat mod p?
if (p % 4 == 3) return powMod(a, (p + 1)/2, p);
if (p % 8 == 5) return powMod(a, (p + 3)/8, p);
ll s = p - 1;
ll r = 0;
while (s % 2 == 0) s /= 2, r++;
ll n = 2;
while (powMod(n, (p - 1)/2, p) != p - 1) n++;
ll x = powMod(a, (s + 1)/2, p);
ll b = powMod(a, s, p);
ll g = powMod(n, s, p);
while (true) {
ll t = b;
ll m = 0;
for (;m < r && t != 1; m++) t = (t * t) % p;
if (t == 1) return x;
ll gs = powMod(g, 1ll << (r - m - 1), p);
g = (gs * gs) % p;
x = (x * gs) % p;
b = (b * g) % p;
r = m;
}}
|
