diff options
Diffstat (limited to 'content/math/sqrtModCipolla.cpp')
| -rw-r--r-- | content/math/sqrtModCipolla.cpp | 14 |
1 files changed, 14 insertions, 0 deletions
diff --git a/content/math/sqrtModCipolla.cpp b/content/math/sqrtModCipolla.cpp new file mode 100644 index 0000000..1fac0c5 --- /dev/null +++ b/content/math/sqrtModCipolla.cpp @@ -0,0 +1,14 @@ +ll sqrtMod(ll a, ll p) {// teste mit legendre ob lösung existiert + if (a < 2) return a; + ll t = 0; + while (legendre((t*t-4*a) % p, p) >= 0) t = rng() % p; + ll b = -t, c = -t, d = 1, m = p; + for (m++; m /= 2; b = (a+a-b*b) % p, a = (a*a) % p) { + if (m % 2) { + d = (c-d*b) % p; + c = (c*a) % p; + } else { + c = (d*a - c*b) % p; + }} + return (d + p) % p; +} |