mzuenni tests

1 files changed, 0 insertions, 23 deletions

diff --git a/math/modSqrt.cpp b/math/modSqrt.cpp
deleted file mode 100644
index 367c6c7..0000000
--- a/math/modSqrt.cpp
+++ /dev/null
@@ -1,23 +0,0 @@
-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;
-}}