mzuenni tests

51 files changed, 2996 insertions, 0 deletions

diff --git a/test/math/berlekampMassey.cpp b/test/math/berlekampMassey.cpp
new file mode 100644
index 0000000..58fd143
--- /dev/null
+++ b/test/math/berlekampMassey.cpp
@@ -0,0 +1,68 @@
+#include "../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/berlekampMassey.cpp>
+
+struct RandomRecurence {
+	vector<ll> f, c, cache;
+	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+	RandomRecurence(const vector<ll>& f_, const vector<ll>& c_) : c(c_), cache(f_) {
+		if (cache.size() < c.size()) cerr << "wrong size" << FAIL;
+		cache.resize(c.size());
+		f = cache;
+	}
+
+	ll operator()(ll k){
+		while (sz(cache) <= k) {
+			ll cur = 0;
+			for (ll i = 0; i < sz(c); i++) {
+				cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+			}
+			cur %= mod;
+			cache.push_back(cur);
+		}
+		return cache[k];
+	}
+};
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 50'000; i++) {
+		int n = Random::integer<int>(1, 10);
+		RandomRecurence expected(n);
+
+		ll k = Random::integer<ll>(2*n, 100);
+		vector<ll> s(k);
+		for (ll j = 0; j < k; j++) s[j] = expected(j);
+
+		auto res = BerlekampMassey(s);
+		RandomRecurence got(s, res);
+
+		for (ll j = 0; j < 3*k; j++) {
+			if (got(j) != expected(j)) cerr << "got: " << got(j) << ", expected: " << expected(j) << FAIL;
+		}
+
+		queries += k;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 5'000;
+void performance_test() {
+	timer t;
+	RandomRecurence f(N);
+	f(2*N);
+	t.start();
+	auto res = BerlekampMassey(f.cache);
+	t.stop();
+	hash_t hash = 0;
+	for (ll x : res) hash += x;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+	
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/bigint.cpp b/test/math/bigint.cpp
new file mode 100644
index 0000000..3fc4ac1
--- /dev/null
+++ b/test/math/bigint.cpp
@@ -0,0 +1,122 @@
+#include "../util.h"
+#include <math/bigint.cpp>
+
+template<ll MOD>
+struct modInt {
+	ll value = 0;
+	modInt() {}
+	modInt(const bigint& x) {
+		stringstream a;
+		a << x;
+		string b = a.str();
+		for (ll i = b[0] == '-' ? 1 : 0; i < sz(b); i++) {
+			value *= 10;
+			value += b[i] - '0';
+			value %= MOD;
+		}
+		if (b[0] == '-') value = (MOD - value) % MOD;
+	}
+
+	modInt(ll x) : value(((x % MOD) + MOD) % MOD) {}
+
+	modInt operator+(modInt o) const {return value + o.value;}
+	modInt operator-(modInt o) const {return value - o.value;}
+	modInt operator*(modInt o) const {return value * o.value;}
+
+	modInt& operator+=(modInt o) {return *this = *this + o;}
+	modInt& operator-=(modInt o) {return *this = *this - o;}
+	modInt& operator*=(modInt o) {return *this = *this * o;}
+
+	ll& operator*() {return value;}
+	bool operator==(const modInt& o) const {return value == o.value;}
+	bool operator!=(const modInt& o) const {return value != o.value;}
+};
+
+constexpr ll MOD = 1'394'633'899;
+constexpr ll POOL = 8;
+
+void stress_test() {
+	int queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		vector<modInt<MOD>> expectedPool(POOL);
+		vector<bigint> gotPool(POOL);
+		for (int i = 0; i < POOL; i++) {
+			ll x = Random::integer<ll>(-1'000'000'000'000'000'000ll, 1'000'000'000'000'000'000ll);
+			expectedPool[i] = x;
+			gotPool[i] = x;
+			if (expectedPool[i] != modInt<MOD>(gotPool[i])) cerr << "error: 0" << FAIL;
+		}
+		for (int i = 0; i < 200; i++) {
+			int a = Random::integer<int>(0, POOL);
+			int b = Random::integer<int>(0, POOL);
+			int o = Random::integer<int>(0, 3);
+
+			if (Random::integer<int>(0, 2) == 0) {//x=
+				auto tmpExpected = expectedPool[a];
+				auto tmpGot = gotPool[a];
+
+				if (o == 0) {
+					tmpExpected += expectedPool[b];
+					tmpGot += gotPool[b];
+				}
+				if (o == 1) {
+					tmpExpected -= expectedPool[b];
+					tmpGot -= gotPool[b];
+				}
+				if (o == 2) {
+					tmpExpected -= expectedPool[b];
+					tmpGot -= gotPool[b];
+				}
+
+				if (tmpExpected != modInt<MOD>(tmpGot)) {
+					cerr << gotPool[a];
+					if (o == 0) cerr << "+";
+					if (o == 1) cerr << "-";
+					if (o == 2) cerr << "*";
+					cerr << gotPool[b] << "=" << tmpGot << endl;
+					cerr << "error: 1" << FAIL;
+				}
+
+				expectedPool[b] = tmpExpected;
+				gotPool[b] = tmpGot;
+			} else {//x
+				int c = Random::integer<int>(0, POOL);
+
+				modInt<MOD> tmpExpected;
+				bigint tmpGot;
+
+				if (o == 0) {
+					tmpExpected = expectedPool[a] + expectedPool[b];
+					tmpGot = gotPool[a] + gotPool[b];
+				}
+				if (o == 1) {
+					tmpExpected = expectedPool[a] - expectedPool[b];
+					tmpGot = gotPool[a] - gotPool[b];
+				}
+				if (o == 2) {
+					tmpExpected = expectedPool[a] * expectedPool[b];
+					tmpGot = gotPool[a] * gotPool[b];
+				}
+
+				if (tmpExpected != modInt<MOD>(tmpGot)) {
+					cerr << gotPool[a];
+					if (o == 0) cerr << "+";
+					if (o == 1) cerr << "-";
+					if (o == 2) cerr << "*";
+					cerr << gotPool[b] << "=" << tmpGot << endl;
+					cerr << "error: 2" << FAIL;
+				}
+
+				expectedPool[c] = tmpExpected;
+				gotPool[c] = tmpGot;
+			}
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+	
+int main() {
+	stress_test();
+}
+
diff --git a/test/math/binomial0.cpp b/test/math/binomial0.cpp
new file mode 100644
index 0000000..00c04d4
--- /dev/null
+++ b/test/math/binomial0.cpp
@@ -0,0 +1,31 @@
+#include "../util.h"
+#include <math/extendedEuclid.cpp>
+#include <math/multInv.cpp>
+constexpr ll mod = 1'394'633'899;
+#include <math/binomial0.cpp>
+
+
+void stress_test() {
+	vector<ll> last = {1};
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		for (ll j = 0; j <= i; j++) {
+			ll got = calc_binom(i, j);
+			ll expected = last[j];
+			if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += sz(last);
+
+		last.push_back(1);
+		for (ll j = i; j > 0; j--) {
+			last[j] = (last[j] + last[j - 1]) % mod;
+		}
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+int main() {
+	precalc();
+	stress_test();
+}
+
diff --git a/test/math/binomial1.cpp b/test/math/binomial1.cpp
new file mode 100644
index 0000000..f6fe20b
--- /dev/null
+++ b/test/math/binomial1.cpp
@@ -0,0 +1,27 @@
+#include "../util.h"
+#include <math/binomial1.cpp>
+
+
+void stress_test() {
+	vector<ll> last = {1};
+	ll queries = 0;
+	for (ll i = 0; i <= 61; i++) {
+		for (ll j = 0; j <= i; j++) {
+			ll got = calc_binom(i, j);
+			ll expected = last[j];
+			if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += sz(last);
+
+		last.push_back(1);
+		for (ll j = i; j > 0; j--) {
+			last[j] = last[j] + last[j - 1];
+		}
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+}
+
diff --git a/test/math/binomial2.cpp b/test/math/binomial2.cpp
new file mode 100644
index 0000000..b55c8af
--- /dev/null
+++ b/test/math/binomial2.cpp
@@ -0,0 +1,29 @@
+#include "../util.h"
+#include <math/primeSieve.cpp>
+#include <math/binomial2.cpp>
+
+
+void stress_test() {
+	vector<ll> last = {1};
+	ll queries = 0;
+	for (ll i = 0; i <= 1000; i++) {
+		for (ll j = 0; j <= i; j++) {
+			ll got = calc_binom(i, j);
+			ll expected = last[j];
+			if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += sz(last);
+
+		last.push_back(1);
+		for (ll j = i; j > 0; j--) {
+			last[j] = (last[j] + last[j - 1]) % mod;
+		}
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+int main() {
+	primeSieve();
+	stress_test();
+}
+
diff --git a/test/math/binomial3.cpp b/test/math/binomial3.cpp
new file mode 100644
index 0000000..4a99689
--- /dev/null
+++ b/test/math/binomial3.cpp
@@ -0,0 +1,31 @@
+#include "../util.h"
+#include <math/extendedEuclid.cpp>
+#include <math/multInv.cpp>
+#include <math/binomial3.cpp>
+
+
+constexpr ll mod = 503;
+
+void stress_test() {
+	vector<ll> last = {1};
+	ll queries = 0;
+	for (ll i = 0; i < mod; i++) {
+		for (ll j = 0; j <= i; j++) {
+			ll got = calc_binom(i, j, mod);
+			ll expected = last[j];
+			if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += sz(last);
+
+		last.push_back(1);
+		for (ll j = i; j > 0; j--) {
+			last[j] = (last[j] + last[j - 1]) % mod;
+		}
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+}
+
diff --git a/test/math/chineseRemainder.cpp b/test/math/chineseRemainder.cpp
new file mode 100644
index 0000000..26e71de
--- /dev/null
+++ b/test/math/chineseRemainder.cpp
@@ -0,0 +1,47 @@
+#include "../util.h"
+#include <math/extendedEuclid.cpp>
+#include <math/chineseRemainder.cpp>
+
+struct NAIVE {
+	vector<pair<ll, ll>> added;
+	void add(ll a, ll m) {
+		added.emplace_back(a, m);
+	}
+	ll sol() const {
+		ll n = 1;
+		for (auto [_, x] : added) n = lcm(n, x);
+		for (ll i = 0; i < n; i++) {
+			bool ok = true;
+			for (auto [a, m] : added) {
+				ok &= (i % m) == a;
+			}
+			if (ok) return i;
+		}
+		return -1;
+	}
+};
+
+void stress_test() {
+	ll queries = 0;
+	ll withSol = 0;
+	for (ll i = 0; i < 100'000; i++) {
+		CRT crt;
+		NAIVE naive;
+		for (ll j = 0; j < 3; j++) {
+			int m = Random::integer<int>(1, 50);
+			int a = Random::integer<int>(0, m);
+			crt.add(a, m);
+			naive.add(a, m);
+		}
+		if (crt.hasSol != (naive.sol() >= 0)) cerr << "error" << FAIL;
+		if (crt.hasSol && crt.sol != naive.sol()) cerr << "got: " << (ll)crt.sol << ", expected: " << naive.sol() << FAIL;
+		queries += crt.M;
+		withSol += crt.hasSol;
+	}
+	cerr << "tested queries: " << queries << "(" << withSol << ")" << endl;
+}
+
+int main() {
+	stress_test();
+}
+
diff --git a/test/math/cycleDetection.cpp b/test/math/cycleDetection.cpp
new file mode 100644
index 0000000..1694589
--- /dev/null
+++ b/test/math/cycleDetection.cpp
@@ -0,0 +1,46 @@
+#include "../util.h"
+#include <math/cycleDetection.cpp>
+
+pair<ll, ll> naive(ll x0, function<ll(ll)> f) {
+	map<ll, ll> seen;
+	ll d = 0;
+	while (seen.find(x0) == seen.end()) {
+		seen[x0] = d;
+		d++;
+		x0 = f(x0);
+	}
+	return {seen[x0], d - seen[x0]};
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 1000'000; i++) {
+		int m = Random::integer<int>(1, 100);
+		int c = Random::integer<int>(0, m);
+		auto f = [&](ll x){return (x*x + c) % m;};
+		int x0 = Random::integer<int>(0, m);
+		auto got = cycleDetection(x0, f);
+		auto expected = naive(x0, f);
+		if (got != expected) cerr << "error: " << got.first << " " << got.second << " " << expected.first << " " << expected.second << FAIL;
+		queries += got.second;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr ll M = 18'086'183;
+void performance_test() {
+	timer t;
+	auto f = [&](ll x){return (1337*x + 42) % M;};
+	t.start();
+	auto [a, b] = cycleDetection(42, f);
+	t.stop();
+	hash_t hash = a + b;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/discreteLogarithm.cpp b/test/math/discreteLogarithm.cpp
new file mode 100644
index 0000000..0f9eecf
--- /dev/null
+++ b/test/math/discreteLogarithm.cpp
@@ -0,0 +1,64 @@
+#include "../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/legendre.cpp>
+
+ll overwrite = 0;
+ll getMemory(ll /**/) {return overwrite - 1;} //dlog code adds one...
+#define sqrtl getMemory
+#include <math/discreteLogarithm.cpp>
+#undef sqrtl
+
+template<typename F>
+void stress_test(F&& f) {
+	ll work = 0;
+	for (ll tries = 0; tries < 3'000; tries++) {
+		ll p = Random::prime<ll>(1'000);
+		overwrite = f(p);
+		ll a = Random::integer<ll>(1, p);
+		vector<bool> naive(p);
+		for (ll i = 0, j = 1; i < p; i++, j = (j * a) % p) {
+			naive[j] = true;
+		}
+		for (ll b = 0; b < p; b++) {
+			ll got = dlog(a, b, p);
+			if (got < -1 || got >= p) cerr << "error: out of range" << FAIL;
+			if ((got >= 0) != naive[b]) {
+				cerr << a << " " << b << " " << p << endl;
+				cerr << got << endl;
+				cerr << "error" << FAIL;
+			}
+			if (got >= 0 && powMod(a, got, p) != b) {
+				cerr << a << "^" << got << " = " << powMod(a, got, p) << " != " << b << " % " << p << endl;
+				cerr << "error: wrong" << FAIL;
+			}
+			work++;
+		}
+	}
+	cerr << "stress tested: " << work << endl;
+}
+
+constexpr int N = 25;
+constexpr ll mod = 1'394'633'899;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	overwrite = sqrt(mod);
+	for (int operations = 0; operations < N; operations++) {
+		ll a = Random::integer<ll>(1, mod);
+		ll b = Random::integer<ll>(0, mod);
+		t.start();
+		hash += dlog(a, b, mod);
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+
+int main() {
+	stress_test([](ll p){return sqrtl(p);});
+	stress_test([](ll p){return min<ll>(10, p - 1);});
+	stress_test([](ll p){return min<ll>(p - 1, sqrtl(p) + 100);});
+	performance_test();
+}
+
diff --git a/test/math/discreteNthRoot.cpp b/test/math/discreteNthRoot.cpp
new file mode 100644
index 0000000..d595e6d
--- /dev/null
+++ b/test/math/discreteNthRoot.cpp
@@ -0,0 +1,78 @@
+#include "../util.h"
+#define ll lll
+#include <math/modPowIterativ.cpp>
+#undef ll
+#include <math/millerRabin.cpp>
+#include <math/rho.cpp>
+
+ll phi(ll pk, ll p, ll /*k*/) {return pk - pk / p;}
+ll phi(ll n) { // O(sqrt(n))
+	ll res = 1;
+	for (ll p = 2; p * p <= n; p++) {
+		if (n % p == 0) {
+			ll pk = 1;
+			ll k = 0;
+			do {
+				n /= p;
+				pk *= p;
+				k++;
+			} while (n % p == 0);
+			res *= phi(pk, p, k);
+	}}
+	if (n > 1) res *= phi(n, n, 1);
+	return res;
+}
+
+#include <math/primitiveRoot.cpp>
+#include <math/discreteLogarithm.cpp>
+#include <math/discreteNthRoot.cpp>
+
+//x^a=b mod m
+ll naiveRoot(ll a, ll b, ll m) {
+	for (ll i = 0; i < m; i++) {
+		if (powMod(i, a, m) == b) return i;
+	}
+	return -1;
+}
+
+void stress_test() {
+	int queries = 0;
+	int found = 0;
+	for (int tries = 0; tries < 50'000; tries++) {
+		ll p = Random::prime<ll>(0, 1000);
+		ll a = Random::integer<ll>(1, p);
+		ll b = Random::integer<ll>(1, p);
+
+		ll got = root(a, b, p);
+		ll expected = naiveRoot(a, b, p);
+
+		if (got < -1 || got >= p) cerr << "error: out of range" << FAIL;
+		if (got >= 0 && powMod(got, a, p) != b) cerr << "error: wrong" << FAIL;
+		if ((got >= 0) != (expected >= 0)) cerr << "error" << FAIL;
+		queries++;
+		if (expected >= 0) found++;
+	}
+	cerr << "tested random queries: " << queries << " (" << found << ")" << endl;
+}
+
+constexpr int N = 50;
+constexpr ll mod = 1'394'633'899;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int i = 0; i < N; i++) {
+		ll a = Random::integer<ll>(1, mod);
+		ll b = Random::integer<ll>(1, mod);
+		t.start();
+		hash += root(a, b, mod);
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/divisors.cpp b/test/math/divisors.cpp
new file mode 100644
index 0000000..2402d2a
--- /dev/null
+++ b/test/math/divisors.cpp
@@ -0,0 +1,65 @@
+#include "../util.h"
+#define ll lll
+#include <math/modPowIterativ.cpp>
+#undef ll
+#include <math/millerRabin.cpp>
+
+bool isSquare(ll x) {
+	ll r = sqrtl(x);
+	while (r*r > x) r--;
+	while ((r+1)*(r+1) <= x) r++;
+	return r*r==x;
+}
+
+#include <math/divisors.cpp>
+
+ll naive(ll x) {
+	ll res = 0;
+	for (ll i = 1; i*i <= x; i++) {
+		if (x % i == 0) {
+			res++;
+			if (i*i != x) res++;
+		}
+	}
+	return res;
+}
+
+void stress_test() {
+	ll work = 0;
+	for (ll i = 0; i < 1'000; i++) {
+		ll x = Random::integer<ll>(1, 1'000'000'000'000);
+		auto got = countDivisors(x);
+		auto expected = naive(x);
+		if (got != expected) cerr << "error: " << x << FAIL;
+		work += sqrt(x);
+	}
+	for (ll i = 0; i < 100'000; i++) {
+		ll x = Random::integer<ll>(1, 1'000'000);
+		auto got = countDivisors(x);
+		auto expected = naive(x);
+		if (got != expected) cerr << "error: " << x << FAIL;
+		work += sqrt(x);
+	}
+	cerr << "stress tested: " << work << endl;
+}
+
+constexpr int N = 200;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll x = Random::integer<ll>(1e18 / 2, 1e18);
+		t.start();
+		hash += countDivisors(x);
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/extendedEuclid.cpp b/test/math/extendedEuclid.cpp
new file mode 100644
index 0000000..597f722
--- /dev/null
+++ b/test/math/extendedEuclid.cpp
@@ -0,0 +1,41 @@
+#include "../util.h"
+#include <math/extendedEuclid.cpp>
+
+void stress_test() {
+	if (extendedEuclid(0, 0)[0] != 0) cerr << "error: extendedEuclid(0, 0)" << FAIL;
+	ll queries = 0;
+	timer t;
+	for (int i = 0; i < 1'000'000; i++) {
+		ll a = Random::integer<ll>(0, 1'000'000'000);
+		ll b = 0;
+		{
+			t.start();
+			auto [got, x, y] = extendedEuclid(a, b);
+			t.stop();
+			ll expected = std::gcd(a, b);
+			if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL;
+			if (abs(x) >= max<ll>(2, abs(b))) cerr << "invalid x" << FAIL;
+			if (abs(y) >= max<ll>(2, abs(a))) cerr << "invalid y" << FAIL;
+			if (a*x + b*y != expected) cerr << "invalid x or y" << FAIL;
+		}
+		b = Random::integer<ll>(0, 1'000'000'000);
+		{
+			t.start();
+			auto [got, x, y] = extendedEuclid(a, b);
+			t.stop();
+			ll expected = std::gcd(a, b);
+			if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL;
+			if (abs(x) >= max<ll>(2, abs(b))) cerr << "invalid x" << FAIL;
+			if (abs(y) >= max<ll>(2, abs(a))) cerr << "invalid y" << FAIL;
+			if (a*x + b*y != expected) cerr << "invalid x or y" << FAIL;
+		}
+		queries++;
+	}
+	cerr << "tested random queries: " << queries << endl;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms" << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp
new file mode 100644
index 0000000..37bacce
--- /dev/null
+++ b/test/math/gauss.cpp
@@ -0,0 +1,118 @@
+#include "../util.h"
+constexpr double EPS = 1e-9;
+constexpr int UNIQUE = 1;
+constexpr int INCONSISTENT = 2;
+constexpr int MULTIPLE = 3;
+vector<vector<double>> mat;
+#include <math/gauss.cpp>
+
+vector<vector<double>> inverseMat(const vector<vector<double>>& m) {
+	int n = sz(m);
+	mat = m;
+	for (int i = 0; i < n; i++) {
+		if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL;
+		mat[i].resize(2*n);
+		mat[i][n+i] = 1;
+	}
+	gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs...
+	vector<vector<double>> res(m);
+	for (int i = 0; i < n; i++) {
+		res[i] = vector<double>(mat[i].begin() + n, mat[i].end());
+		for (int j = 0; j < n; j++) {
+			if (j != i && mat[i][j] != 0) cerr << "error: not full rank?" << FAIL;
+			if (j == i && mat[i][j] == 0) cerr << "error: not full rank?" << FAIL;
+		}
+	}
+	return res;
+}
+
+vector<vector<double>> mul(const vector<vector<double>>& a, const vector<vector<double>>& b) {
+	int n = sz(a);
+	int m = sz(b[0]);
+	int x = sz(b);
+	if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL;
+	vector<vector<double>> res(n, vector<double>(m));
+	for (int i = 0; i < n; i++) {
+		for (int j = 0; j < m; j++) {
+			for (int k = 0; k < x; k++) {
+				res[i][j] += a[i][k] * b[k][j];
+			}
+		}
+	}
+	return res;
+}
+
+void test_tiny() {
+	mat = {
+		{1, 2, 3, 4},
+		{0, 5, 6, 7},
+		{0, 0, 8, 9},
+	};
+	if (gauss(sz(mat)) != UNIQUE) cerr << "error: 1" << FAIL;
+
+	mat = {
+		{-1,  1, 0, -1},
+		{ 2,  6, 0, 10},
+		{ 1, -2, 0,  0},
+	};
+	if (gauss(sz(mat)) != MULTIPLE) cerr << "error: 2" << FAIL;
+
+	mat = {
+		{-1,  1, 0, -1},
+		{ 2,  6, 0, 10},
+		{ 1, -2, 0,  1},
+	};
+	if (gauss(sz(mat)) != INCONSISTENT) cerr << "error: 3" << FAIL;
+}
+
+void stress_test_inv() {
+	ll queries = 0;
+	for (int tries = 0; tries < 20'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+
+		vector<vector<double>> m(n);
+		for (auto& v : m) v = Random::reals<double>(n, 0, 1'000);
+		// m hopefully has full rank...
+
+		auto inv = inverseMat(m);
+
+		auto prod = mul(m, inv);
+
+		for (int i = 0; i < n; i++) {
+			for (int j = 0; j < n; j++) {
+				if (i == j && abs(prod[i][j] - 1) >= EPS) cerr << "error: not inverted " << prod[i][j] << FAIL;
+				if (i != j && abs(prod[i][j] - 0) >= EPS) cerr << "error: not inverted " << prod[i][j] << FAIL;
+			}
+		}
+
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 250;
+void performance_test() {
+	timer t;
+
+	vector<vector<double>> m(N);
+	for (auto& v : m) v = Random::reals<double>(N, 0, 1'000);
+	mat = m;
+
+	t.start();
+	gauss(N);
+	t.stop();
+	hash_t hash = 0;
+	for (int i = 0; i < N; i++) {
+		for (int j = 0; j < N; j++) {
+			hash += mat[i][j];
+		}
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	test_tiny();
+	stress_test_inv();
+	performance_test();
+}
diff --git a/test/math/gcd-lcm.cpp b/test/math/gcd-lcm.cpp
new file mode 100644
index 0000000..294095b
--- /dev/null
+++ b/test/math/gcd-lcm.cpp
@@ -0,0 +1,46 @@
+#include "../util.h"
+#include <math/gcd-lcm.cpp>
+
+void stress_test() {
+	if (::gcd(0, 0) != 0) cerr << "error: gcd(0, 0)" << FAIL;
+	if (::lcm(0, 0) != 0) cerr << "error: lcm(0, 0)" << FAIL;
+	ll queries = 0;
+	timer t;
+	for (int i = 0; i < 1'000'000; i++) {
+		ll a = Random::integer<ll>(0, 1'000'000'000);
+		ll b = 0;
+		{
+			ll got = ::gcd(a, b);
+			ll expected = std::gcd(a, b);
+			if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL;
+		}
+		{
+			ll got = ::lcm(a, b);
+			ll expected = std::lcm(a, b);
+			if (got != expected) cerr << "lcm(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL;
+		}
+		b = Random::integer<ll>(0, 1'000'000'000);
+		{
+			t.start();
+			ll got = ::gcd(a, b);
+			t.stop();
+			ll expected = std::gcd(a, b);
+			if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL;
+		}
+		{
+			t.start();
+			ll got = ::lcm(a, b);
+			t.stop();
+			ll expected = std::lcm(a, b);
+			if (got != expected) cerr << "lcm(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries++;
+	}
+	cerr << "tested random queries: " << queries << endl;
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms" << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/math/goldenSectionSearch.cpp b/test/math/goldenSectionSearch.cpp
new file mode 100644
index 0000000..565a21c
--- /dev/null
+++ b/test/math/goldenSectionSearch.cpp
@@ -0,0 +1,74 @@
+#include "../util.h"
+#include <math/goldenSectionSearch.cpp>
+
+struct RandomFunction {
+	ld min;
+	vector<pair<ld, int>> polys;
+	RandomFunction(ld l, ld r) : min(Random::real<ld>(l, r)) {
+		do {
+			polys.emplace_back(
+				Random::real<ld>(0, 1e9),
+				2 * Random::integer<int>(1, 5)
+			);
+		} while(false && Random::integer<int>(4) != 0);
+	}
+
+	ld operator()(ld x){
+		ld res = 0;
+		for (auto [m, p] : polys) {
+			res += m * pow(x - min, p);
+		}
+		return res;
+	}
+
+	friend ostream& operator<<(ostream& os, const RandomFunction& f) {
+		string plus = "";
+		for (auto [m, p] : f.polys) {
+			os << setprecision(15) << plus << m << "*(x-" << f.min << ")**" << p;
+			plus = "+";
+		}
+		return os;
+	}
+};
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 50'000; i++) {
+		ld l = Random::real<double>(-200, 200);
+		ld r = Random::real<double>(-200, 200);
+		if (l > r) swap(l, r);
+
+		RandomFunction f(l, r);
+
+		ld got = gss(l, r, f);
+		ld expected = f.min;
+		if (float_error(got, expected) > 1e-6) {
+			cerr << f << endl;
+			cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries++;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 10'000;
+void performance_test() {
+	timer t;
+	RandomFunction f(-200, 200);
+	f.polys.resize(1);
+
+	hash_t hash = 0;
+	for (int i = 0; i < N; i++) {
+		t.start();
+		hash += gss(-200, 200, f);
+		t.stop();
+	}
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/inversions.cpp b/test/math/inversions.cpp
new file mode 100644
index 0000000..bd362eb
--- /dev/null
+++ b/test/math/inversions.cpp
@@ -0,0 +1,42 @@
+#include "../util.h"
+#include <math/inversions.cpp>
+
+ll naive(const vector<ll>& v) {
+	ll res = 0;
+	for (ll i = 0; i < sz(v); i++) {
+		for (ll j = 0; j < i; j++) {
+			if (v[j] > v[i]) res++;
+		}
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 100'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		auto v = Random::integers<ll>(n, -50, 50);
+		ll got = inversions(v);
+		ll expected = naive(v);
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+	auto v = Random::integers<ll>(N, -10'000, 10'000);
+	t.start();
+	hash_t hash = inversions(v);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp
new file mode 100644
index 0000000..85ab0d2
--- /dev/null
+++ b/test/math/inversionsMerge.cpp
@@ -0,0 +1,46 @@
+#include "../util.h"
+#include <math/inversionsMerge.cpp>
+
+ll naive(const vector<ll>& v) {
+	ll res = 0;
+	for (ll i = 0; i < sz(v); i++) {
+		for (ll j = 0; j < i; j++) {
+			if (v[j] > v[i]) res++;
+		}
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 100'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		vector<ll> v(n);
+		for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000);//values must be unique ):
+		shuffle(all(v), Random::rng);
+		ll expected = naive(v);
+		ll got = mergeSort(v);
+		if (got != expected) {
+			cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 2'000'000; //10 times faster
+void performance_test() {
+	timer t;
+	auto v = Random::integers<ll>(N, -10'000, 10'000);
+	t.start();
+	hash_t hash = mergeSort(v);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/kthperm.cpp b/test/math/kthperm.cpp
new file mode 100644
index 0000000..8115356
--- /dev/null
+++ b/test/math/kthperm.cpp
@@ -0,0 +1,37 @@
+#include "../util.h"
+#include <math/kthperm.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		vector<ll> expected(n);
+		iota(all(expected), 0);
+		ll k = 0;
+		do {
+			auto got = kthperm(n, k);
+			if (got != expected) cerr << "error" << FAIL;
+			k++;
+		} while (k < 100 && next_permutation(all(expected)));
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 500'000;
+void performance_test() {
+	timer t;
+	t.start();
+	auto got = kthperm(N, 4'168'751'907'498'170ll);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * got[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/kthperm_permIndex.cpp b/test/math/kthperm_permIndex.cpp
new file mode 100644
index 0000000..5e05c73
--- /dev/null
+++ b/test/math/kthperm_permIndex.cpp
@@ -0,0 +1,20 @@
+#include "../util.h"
+#include <math/kthperm.cpp>
+#include <math/permIndex.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		ll n = Random::integer<ll>(20, 1000);
+		ll expected = Random::integer<ll>(0, 1'000'000'000'000'000'000);
+		ll got = permIndex(kthperm(n, expected));
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+}
+
diff --git a/test/math/legendre.cpp b/test/math/legendre.cpp
new file mode 100644
index 0000000..f210b57
--- /dev/null
+++ b/test/math/legendre.cpp
@@ -0,0 +1,43 @@
+#include "../util.h"
+#define ll lll
+#include <math/modPowIterativ.cpp>
+#undef ll
+#include <math/legendre.cpp>
+
+void stress_test() {
+	ll work = 0;
+	for (ll i = 0; i < 5'000; i++) {
+		ll p = Random::prime<ll>(5'000);
+		vector<bool> isSquare(p);
+		for (ll j = 1; j < p; j++) isSquare[(j*j) % p] = true;
+		for (ll j = 0; j < p; j++) {			
+			auto got = legendre(j, p);
+			auto expected = j == 0 ? 0 : (isSquare[j] ? 1 : -1);
+			if (got != expected) cerr << "error: " << j << " " << p << FAIL;
+		}
+		work += p;
+	}
+	cerr << "stress tested: " << work << endl;
+}
+
+constexpr int N = 1'000'000;
+constexpr ll mod = 1'394'633'899;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll j = Random::integer<ll>(mod);
+		t.start();
+		hash += legendre(j, mod);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/lgsFp.cpp b/test/math/lgsFp.cpp
new file mode 100644
index 0000000..08f8f84
--- /dev/null
+++ b/test/math/lgsFp.cpp
@@ -0,0 +1,118 @@
+#include "../util.h"
+#include <math/shortModInv.cpp>
+vector<vector<ll>> mat;
+#include <math/lgsFp.cpp>
+
+constexpr ll mod = 1'000'000'007;
+
+vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) {
+	int n = sz(m);
+	mat = m;
+	for (int i = 0; i < n; i++) {
+		if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL;
+		mat[i].resize(2*n);
+		mat[i][n+i] = 1;
+	}
+	gauss(n, mod);
+	vector<vector<ll>> res(m);
+	for (int i = 0; i < n; i++) {
+		res[i] = vector<ll>(mat[i].begin() + n, mat[i].end());
+		for (int j = 0; j < n; j++) {
+			if (j != i && mat[i][j] != 0) cerr << "error: not full rank?" << FAIL;
+			if (j == i && mat[i][j] != 1) cerr << "error: not full rank?" << FAIL;
+		}
+	}
+	return res;
+}
+
+vector<vector<ll>> mul(const vector<vector<ll>>& a, const vector<vector<ll>>& b) {
+	int n = sz(a);
+	int m = sz(b[0]);
+	int x = sz(b);
+	if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL;
+	vector<vector<ll>> res(n, vector<ll>(m));
+	for (int i = 0; i < n; i++) {
+		for (int j = 0; j < m; j++) {
+			for (int k = 0; k < x; k++) {
+				res[i][j] += a[i][k] * b[k][j];
+				res[i][j] %= mod;
+			}
+		}
+	}
+	return res;
+}
+
+//this should just not crash...
+void test_square() {
+	ll queries = 0;
+	hash_t hash = 0;
+	for (int tries = 0; tries < 1'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+
+		vector<vector<ll>> m(n);
+		for (auto& v : m) v = Random::integers<ll>(n, 0, mod);
+		mat = m;
+		gauss(n, mod);
+
+		for (int i = 0; i < n; i++) {
+			for (int j = 0; j < n; j++) {
+				hash += mat[i][j];
+			}
+		}
+
+		queries += n;
+	}
+	cerr << "tested sqaures: " << queries << " (hash: " << hash << ")" << endl;;
+}
+
+void stress_test_inv() {
+	ll queries = 0;
+	for (int tries = 0; tries < 20'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+
+		vector<vector<ll>> m(n);
+		for (auto& v : m) v = Random::integers<ll>(n, 0, mod);
+		// m hopefully has full rank...
+
+		auto inv = inverseMat(m);
+
+		auto prod = mul(m, inv);
+
+		for (int i = 0; i < n; i++) {
+			for (int j = 0; j < n; j++) {
+				if (i == j && prod[i][j] != 1) cerr << "error: not inverted" << FAIL;
+				if (i != j && prod[i][j] != 0) cerr << "error: not inverted" << FAIL;
+			}
+		}
+
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 250;
+void performance_test() {
+	timer t;
+
+	vector<vector<ll>> m(N);
+	for (auto& v : m) v = Random::integers<ll>(N, 0, mod);
+	mat = m;
+
+	t.start();
+	gauss(N, mod);
+	t.stop();
+	hash_t hash = 0;
+	for (int i = 0; i < N; i++) {
+		for (int j = 0; j < N; j++) {
+			hash += mat[i][j];
+		}
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	test_square();
+	stress_test_inv();
+	performance_test();
+}
diff --git a/test/math/linearCongruence.cpp b/test/math/linearCongruence.cpp
new file mode 100644
index 0000000..ba8eeac
--- /dev/null
+++ b/test/math/linearCongruence.cpp
@@ -0,0 +1,53 @@
+#include "../util.h"
+#include <math/extendedEuclid.cpp>
+#include <math/multInv.cpp>
+#include <math/linearCongruence.cpp>
+
+ll naive(ll a, ll b, ll m) {
+	for (ll x = 0; x < m; x++) {
+		if ((a * x) % m == b) return x;
+	}
+	return -1;
+}
+
+void stress_test() {
+	ll work = 0;
+	ll positive = 0;
+	for (ll tries = 0; tries < 500'000; tries++) {
+		ll m = Random::integer<ll>(0, 1'000);
+		ll a = Random::integer<ll>(0, m);
+		ll b = Random::integer<ll>(0, m);
+
+		ll got = solveLinearCongruence(a, b, m);
+		ll expected = naive(a, b, m);
+
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << endl;
+		work++;
+		if (got >= 0) positive++;
+	}
+	cerr << "stress tested: " << work << " (" << positive << ")" << endl;
+}
+
+constexpr int N = 500'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll m = Random::integer<ll>(0, 1'0000'000'000);
+		ll a = Random::integer<ll>(0, m);
+		ll b = Random::integer<ll>(0, m);
+
+		t.start();
+		hash += solveLinearCongruence(a, b, m);
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp
new file mode 100644
index 0000000..21a8a7c
--- /dev/null
+++ b/test/math/linearRecurrence.cpp
@@ -0,0 +1,54 @@
+#include "../util.h"
+#include <math/linearRecurrence.cpp>
+
+struct RandomRecurence {
+	vector<ll> f, c, cache;
+	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+
+	ll operator()(ll k){
+		while (sz(cache) <= k) {
+			ll cur = 0;
+			for (ll i = 0; i < sz(c); i++) {
+				cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+			}
+			cur %= mod;
+			cache.push_back(cur);
+		}
+		return cache[k];
+	}
+};
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 10);
+		RandomRecurence f(n);
+		for (int j = 0; j < 100; j++) {
+			ll k = Random::integer<ll>(0, 1000);
+
+			ll got = kthTerm(f.f, f.c, k);
+			ll expected = f(k);
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000;
+void performance_test() {
+	timer t;
+	RandomRecurence f(N);
+	t.start();
+	hash_t hash = kthTerm(f.f, f.c, 1e18);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/linearSieve.cpp b/test/math/linearSieve.cpp
new file mode 100644
index 0000000..8ea822b
--- /dev/null
+++ b/test/math/linearSieve.cpp
@@ -0,0 +1,71 @@
+#include "../util.h"
+namespace expected {
+#include <math/primeSieve.cpp>
+}
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#include <math/linearSieve.cpp>
+
+void stress_test() {
+	expected::primeSieve();
+	expected::primes.resize(primes.size());
+	if (expected::primes != primes) cerr << "error: primes" << FAIL;
+	int queries = 0;
+	for (int i = 1; i < 1'000'000; i++) {
+		auto got = sieved[i];
+		auto expected = naive(i);
+		if (got != expected) cerr << i << ", got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	for (int i = 0; i < 1'000'000; i++) {
+		ll x = Random::integer<ll>(2, N);
+		auto got = sieved[x];
+		auto expected = naive(x);
+		if (got != expected) cerr << x << ", got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+void test_tiny() {
+	if (mu( 3, 3, 1) != -1) cerr << "error: 1" << FAIL;
+	if (mu( 9, 3, 2) !=  0) cerr << "error: 2" << FAIL;
+	if (mu(27, 3, 3) !=  0) cerr << "error: 3" << FAIL;
+
+	if (phi( 3, 3, 1) !=  2) cerr << "error: 4" << FAIL;
+	if (phi( 9, 3, 2) !=  6) cerr << "error: 5" << FAIL;
+	if (phi(27, 3, 3) != 18) cerr << "error: 6" << FAIL;
+
+	if (div( 3, 3, 1) !=  2) cerr << "error: 7" << FAIL;
+	if (div( 9, 3, 2) !=  3) cerr << "error: 8" << FAIL;
+	if (div(27, 3, 3) !=  4) cerr << "error: 9" << FAIL;
+
+	if (divSum( 3, 3, 1) !=  4) cerr << "error: 10" << FAIL;
+	if (divSum( 9, 3, 2) != 13) cerr << "error: 11" << FAIL;
+	if (divSum(27, 3, 3) != 40) cerr << "error: 12" << FAIL;
+
+	if (square( 3, 3, 1) !=  1) cerr << "error: 13" << FAIL;
+	if (square( 9, 3, 2) !=  9) cerr << "error: 14" << FAIL;
+	if (square(27, 3, 3) !=  9) cerr << "error: 15" << FAIL;
+
+	if (squareFree( 3, 3, 1) !=  3) cerr << "error: 13" << FAIL;
+	if (squareFree( 9, 3, 2) !=  3) cerr << "error: 14" << FAIL;
+	if (squareFree(27, 3, 3) !=  3) cerr << "error: 15" << FAIL;
+	cerr << "tested tiny" << endl;
+}
+
+void performance_test() {
+	timer t;
+	t.start();
+	sieve();
+	hash_t hash = sz(primes);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	performance_test();
+	stress_test();
+	test_tiny();
+}
+
diff --git a/test/math/longestIncreasingSubsequence.cpp b/test/math/longestIncreasingSubsequence.cpp
new file mode 100644
index 0000000..407dafe
--- /dev/null
+++ b/test/math/longestIncreasingSubsequence.cpp
@@ -0,0 +1,76 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+#include <math/longestIncreasingSubsequence.cpp>
+#define lis unstrictLis
+#define lower_bound upper_bound
+#include <math/longestIncreasingSubsequence.cpp>
+#undef lower_bound
+#undef lis
+
+template<bool STRICT>
+bool isLis(const vector<ll>& a, const vector<int>& lis) {
+	for (int i = 1; i < sz(lis); i++) {
+		if (lis[i-1] >= lis[i]) return false;
+		if (a[lis[i-1]] > a[lis[i]]) return false;
+		if (STRICT && a[lis[i-1]] == a[lis[i]]) return false;
+	}
+	return true;
+}
+
+template<bool STRICT>
+vector<int> naive(const vector<ll>& a) {
+	vector<int> res;
+	for (ll i = 1; i < (1ll << sz(a)); i++) {
+		vector<int> tmp;
+		for (ll j = 0; j < sz(a); j++) {
+			if (((i >> j) & 1) != 0) tmp.push_back(j);
+		}
+		if (sz(tmp) >= sz(res) && isLis<STRICT>(a, tmp)) res = tmp;
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 12);
+		auto a = Random::integers<ll>(n, -10, 10);
+		auto expected = naive<true>(a);
+		auto got = lis(a);
+		if (got != expected) cerr << "error: strict" << FAIL;
+		queries += n;
+	}
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 12);
+		auto a = Random::integers<ll>(n, -10, 10);
+		auto expected = naive<false>(a);
+		auto got = unstrictLis(a);
+		if (got != expected) cerr << "error: not strict" << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	auto a = Random::integers<ll>(N, -10'000, 10'000);
+	auto b = Random::integers<ll>(N, -10'000, 10'000);
+	sort(all(b));
+	auto c = Random::integers<ll>(N, -10'000, 10'000);
+	sort(all(c));
+	reverse(all(c));
+	hash_t hash = 0;
+	t.start();
+	hash += lis(a).size();
+	hash += lis(b).size();
+	hash += lis(c).size();
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/math/matrixPower.cpp b/test/math/matrixPower.cpp
new file mode 100644
index 0000000..4dfb0a8
--- /dev/null
+++ b/test/math/matrixPower.cpp
@@ -0,0 +1,116 @@
+#include "../util.h"
+
+constexpr ll mod = 1'394'633'899;
+
+struct mat {
+	vector<vector<ll>> m;
+	mat(int dim = 0, int diag = 1) : m(dim, vector<ll>(dim)) {
+		for (int i = 0; i < dim; i++) m[i][i] = diag;
+	}
+	mat(const vector<ll> c) : m(sz(c), vector<ll>(sz(c))) {
+		m[0] = c;
+		for (ll i = 1; i < sz(c); i++) {
+			m[i][i-1] = 1;
+		}
+	}
+
+	mat operator*(const mat& o) const {
+		int dim = sz(m);
+		mat res(dim, 0);
+		for (int i = 0; i < dim; i++) {
+			for (int j = 0; j < dim; j++) {
+				for (int k = 0; k < dim; k++) {
+					res.m[i][j] += m[i][k] * o.m[k][j];
+					res.m[i][j] %= mod;
+				}
+			}
+		}
+		return res;
+	}
+
+	vector<ll> operator*(const vector<ll>& o) const {
+		int dim = sz(m);
+		vector<ll> res(dim);
+		for (int i = 0; i < dim; i++) {
+			for (int j = 0; j < dim; j++) {
+				res[i] += m[i][j] * o[j];
+				res[i] %= mod;
+			}
+		}
+		return res;
+	}
+};
+
+#include <math/matrixPower.cpp>
+
+struct RandomRecurence {
+	vector<ll> f, c, cache;
+	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+
+	ll operator()(ll k){
+		while (sz(cache) <= k) {
+			ll cur = 0;
+			for (ll i = 0; i < sz(c); i++) {
+				cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+			}
+			cur %= mod;
+			cache.push_back(cur);
+		}
+		return cache[k];
+	}
+};
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 10);
+		RandomRecurence f(n);
+		precalc(mat(f.c));
+		auto tmp = f.f;
+		reverse(all(tmp));
+
+		for (int j = 0; j < 100; j++) {
+			ll k = Random::integer<ll>(0, 1000);
+
+			vector<ll> got = calc(k, tmp);
+			vector<ll> expected(sz(f.f));
+			for (ll l = 0; l < n; l++) expected[n - 1 - l] = f(k + l);
+
+			if (got != expected) cerr << "error" << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 100;
+constexpr int M = 500;
+void performance_test() {
+	timer t;
+	RandomRecurence f(N);
+	auto tmp = f.f;
+	reverse(all(tmp));
+
+	t.start();
+	precalc(mat(f.c));
+	t.stop();
+	if (t.time > 500) cerr << "too slow precalc: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms" << endl;
+
+	t.reset();
+	hash_t hash = 0;
+	for (int i = 0; i < M; i++) {
+		ll k = Random::integer<ll>(1e17,1e18);
+		t.start();
+		hash += calc(k, tmp).back();
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/millerRabin.base32.cpp b/test/math/millerRabin.base32.cpp
new file mode 100644
index 0000000..742d353
--- /dev/null
+++ b/test/math/millerRabin.base32.cpp
@@ -0,0 +1,137 @@
+#include "../util.h"
+#define ll lll
+#include <math/modPowIterativ.cpp>
+#undef ll
+
+//this is hacky...
+#define bool }\
+constexpr auto bases64 = c20::to_array(ignore::bases32);\
+bool
+namespace ignore {
+#include <math/millerRabin.cpp>
+#undef bool
+
+bool naive(ll x) {
+	for (ll i = 2; i*i <= x; i++) {
+		if (x % i == 0) return false;
+	}
+	return x > 1;
+}
+
+ll mul(const map<ll, int>& facts) {
+	ll res = 1;
+	for (auto [p, c] : facts) {
+		for (int i = 0; i < c; i++) res *= p;
+	}
+	if (abs(res) > (1ll << 62)) cerr << "invalid number: " << res << FAIL;
+	return res;
+}
+
+void extra_tests() {
+	vector<map<ll, int>> test = {
+		{{-1, 1}, {1, 1}},
+		{{-2, 1}, {1, 1}},
+		{{-7, 1}, {1, 1}},
+		{{-19812365821, 1}, {1, 1}},
+		{}, // 1
+		{{2, 1}},
+		{{3, 1}},
+		{{2, 2}},
+		{{5, 1}},
+		{{2, 1}, {3, 1}},
+		{{2, 2}, {3, 1}},
+		{{2, 1}, {3, 2}},
+		{{2, 2}, {3, 2}},
+		{{2, 62}},
+		{{2, 18}, {5, 18}},
+		{{352523, 1}, {352817, 1}},
+		{{41, 1}, {71, 1}, {421, 1}, {811, 1}},
+		{{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}},
+		{{500000003, 1}, {1999999973, 1}},
+		{{65537, 2}},
+		{{999665081, 1}, {999716071, 1}},
+		{{550177, 1}, {1100353, 1}, {1650529, 1}},
+		{{459397, 1}, {918793, 1}, {1378189, 1}},
+		{{37, 1}, {109, 1}},
+		{{31, 1}, {151, 1}},
+		{{239, 1}, {1429, 1}},
+		{{89, 1}, {1093, 1}},
+		{{2, 3}, {15800133918749317, 1}},
+		{{12251, 1}, {85751, 1}},
+		{{3, 1}, {5, 3}, {131, 1}, {6855593, 1}},
+		{{5, 1}, {1927962474784631, 1}},
+		{{197279, 1}, {1775503, 1}},
+		{{3716371, 1}, {14865481, 1}},
+		{{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}},
+		{{4880401, 1}, {9760801, 1}},
+		{{2822159, 1}, {11288633, 1}},
+		{{3290341, 1}, {6580681, 1}},
+		{{611557, 1}, {1834669, 1}},
+		{{9227, 1}, {894923, 1}, {968731, 1}},
+		{{3, 4}, {13, 1}, {62633, 2}},
+		{{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}},
+		{{332721269, 1}, {560937673, 1}},
+		{{30702523, 1}, {122810089, 1}},
+		{{24786439, 1}, {123932191, 1}},
+		{{382500329, 1}, {1530001313, 1}},
+		{{2, 4}, {5, 4}, {13, 1}, {30839, 2}},
+		{{3, 1}, {385417, 1}, {7985344259, 1}},
+		{{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}},
+		{{627838711, 1}, {1212379867, 1}},
+		{{3, 5}, {5, 3}, {41, 2}, {157321, 2}},
+		{{5, 2}, {13, 1}},
+		{{3, 1}, {5, 5}},
+		{{2, 1}, {73, 1}, {193, 1}},
+		{{5, 2}, {13, 1}, {19, 1}, {73, 1}},
+		{{2, 3}, {3, 1}, {407521, 1}},
+		{{2, 1}, {3, 1}, {299210837, 1}},
+		{{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}},
+	};
+
+	timer t;
+	for (auto factors : test) {
+		ll x = mul(factors);
+		if (x >= 1ll << 32) continue;
+		t.start();
+		auto got = isPrime(x);
+		t.stop();
+		bool expected = sz(factors) == 1 && factors.begin()->second == 1;
+		if (got != expected) cerr << "error: " << x << FAIL;
+	}
+	if (t.time > 10) cerr << "too slow" << FAIL;
+	cerr << "stress tested: " << t.time << "ms" << endl;
+}
+
+void stress_test() {
+	ll work = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		ll x = Random::integer<ll>(1, 1ll << 32);
+		auto got = isPrime(x);
+		auto expected = naive(x);
+		if (got != expected) cerr << "error: " << x << FAIL;
+		work += sqrt(x);
+	}
+	cerr << "stress tested: " << work << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll x = Random::integer<ll>(1ll << 31, 1ll << 32);
+		t.start();
+		hash += isPrime(x);
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+
+int main() {
+	extra_tests();
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/millerRabin.cpp b/test/math/millerRabin.cpp
new file mode 100644
index 0000000..fd98586
--- /dev/null
+++ b/test/math/millerRabin.cpp
@@ -0,0 +1,129 @@
+#include "../util.h"
+#define ll lll
+#include <math/modPowIterativ.cpp>
+#undef ll
+#include <math/millerRabin.cpp>
+
+bool naive(ll x) {
+	for (ll i = 2; i*i <= x; i++) {
+		if (x % i == 0) return false;
+	}
+	return x > 1;
+}
+
+ll mul(const map<ll, int>& facts) {
+	ll res = 1;
+	for (auto [p, c] : facts) {
+		for (int i = 0; i < c; i++) res *= p;
+	}
+	if (abs(res) > (1ll << 62)) cerr << "invalid number: " << res << FAIL;
+	return res;
+}
+
+void extra_tests() {
+	vector<map<ll, int>> test = {
+		{{-1, 1}, {1, 1}},
+		{{-2, 1}, {1, 1}},
+		{{-7, 1}, {1, 1}},
+		{{-19812365821, 1}, {1, 1}},
+		{}, // 1
+		{{2, 1}},
+		{{3, 1}},
+		{{2, 2}},
+		{{5, 1}},
+		{{2, 1}, {3, 1}},
+		{{2, 2}, {3, 1}},
+		{{2, 1}, {3, 2}},
+		{{2, 2}, {3, 2}},
+		{{2, 62}},
+		{{2, 18}, {5, 18}},
+		{{352523, 1}, {352817, 1}},
+		{{41, 1}, {71, 1}, {421, 1}, {811, 1}},
+		{{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}},
+		{{500000003, 1}, {1999999973, 1}},
+		{{65537, 2}},
+		{{999665081, 1}, {999716071, 1}},
+		{{550177, 1}, {1100353, 1}, {1650529, 1}},
+		{{459397, 1}, {918793, 1}, {1378189, 1}},
+		{{37, 1}, {109, 1}},
+		{{31, 1}, {151, 1}},
+		{{239, 1}, {1429, 1}},
+		{{89, 1}, {1093, 1}},
+		{{2, 3}, {15800133918749317, 1}},
+		{{12251, 1}, {85751, 1}},
+		{{3, 1}, {5, 3}, {131, 1}, {6855593, 1}},
+		{{5, 1}, {1927962474784631, 1}},
+		{{197279, 1}, {1775503, 1}},
+		{{3716371, 1}, {14865481, 1}},
+		{{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}},
+		{{4880401, 1}, {9760801, 1}},
+		{{2822159, 1}, {11288633, 1}},
+		{{3290341, 1}, {6580681, 1}},
+		{{611557, 1}, {1834669, 1}},
+		{{9227, 1}, {894923, 1}, {968731, 1}},
+		{{3, 4}, {13, 1}, {62633, 2}},
+		{{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}},
+		{{332721269, 1}, {560937673, 1}},
+		{{30702523, 1}, {122810089, 1}},
+		{{24786439, 1}, {123932191, 1}},
+		{{382500329, 1}, {1530001313, 1}},
+		{{2, 4}, {5, 4}, {13, 1}, {30839, 2}},
+		{{3, 1}, {385417, 1}, {7985344259, 1}},
+		{{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}},
+		{{627838711, 1}, {1212379867, 1}},
+		{{3, 5}, {5, 3}, {41, 2}, {157321, 2}},
+		{{5, 2}, {13, 1}},
+		{{3, 1}, {5, 5}},
+		{{2, 1}, {73, 1}, {193, 1}},
+		{{5, 2}, {13, 1}, {19, 1}, {73, 1}},
+		{{2, 3}, {3, 1}, {407521, 1}},
+		{{2, 1}, {3, 1}, {299210837, 1}},
+		{{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}},
+	};
+
+	timer t;
+	for (auto factors : test) {
+		ll x = mul(factors);
+		t.start();
+		auto got = isPrime(x);
+		t.stop();
+		bool expected = sz(factors) == 1 && factors.begin()->second == 1;
+		if (got != expected) cerr << "error: " << x << FAIL;
+	}
+	if (t.time > 10) cerr << "too slow" << FAIL;
+	cerr << "stress tested: " << t.time << "ms" << endl;
+}
+
+void stress_test() {
+	ll work = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		ll x = Random::integer<ll>(1, 1'000'000'000'000);
+		auto got = isPrime(x);
+		auto expected = naive(x);
+		if (got != expected) cerr << "error: " << x << FAIL;
+		work += sqrt(x);
+	}
+	cerr << "stress tested: " << work << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll x = Random::integer<ll>(1e18 / 2, 1e18);
+		t.start();
+		hash += isPrime(x);
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+
+int main() {
+	extra_tests();
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/modExp.cpp b/test/math/modExp.cpp
new file mode 100644
index 0000000..ebb38eb
--- /dev/null
+++ b/test/math/modExp.cpp
@@ -0,0 +1,42 @@
+#include "../util.h"
+#include <math/modExp.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int a = Random::integer<int>(1, 100);
+		int n = Random::integer<int>(2, 100);
+		ll expected = 1;
+		ll k = 0;
+		do {
+			auto got = powMod(a, k, n);
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			k++;
+			expected = (expected * a) % n;
+		} while (k < 100);
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll a = Random::integer<ll>(0, 1'000'000'000);
+		ll b = Random::integer<ll>(0, 1'000'000'000);
+		ll n = Random::integer<ll>(2, 1'000'000'000);
+		t.start();
+		hash += powMod(a, b, n);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/modMulIterativ.cpp b/test/math/modMulIterativ.cpp
new file mode 100644
index 0000000..4f794c5
--- /dev/null
+++ b/test/math/modMulIterativ.cpp
@@ -0,0 +1,57 @@
+#include "../util.h"
+#include <math/modMulIterativ.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int a = Random::integer<int>(1, 100);
+		int n = Random::integer<int>(2, 100);
+		ll expected = 0;
+		ll k = 0;
+		do {
+			auto got = mulMod(a, k, n);
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			k++;
+			expected = (expected + a) % n;
+		} while (k < 100);
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+void stress_test_large() {
+	ll queries = 0;
+	for (ll i = 0; i < 1000'000; i++) {
+		ll a = Random::integer<ll>(0, 1'000'000'000'000'000'000);
+		ll b = Random::integer<ll>(0, 1'000'000'000'000'000'000);
+		ll n = Random::integer<ll>(2, 1'000'000'000'000'000'000);
+		ll expected = (lll)a * b % n;
+		auto got = mulMod(a, b, n);
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 500'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll a = Random::integer<ll>(0, 1'000'000'000'000'000'000);
+		ll b = Random::integer<ll>(0, 1'000'000'000'000'000'000);
+		ll n = Random::integer<ll>(2, 1'000'000'000'000'000'000);
+		t.start();
+		hash += mulMod(a, b, n);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	stress_test_large();
+	performance_test();
+}
+
diff --git a/test/math/modPowIterativ.cpp b/test/math/modPowIterativ.cpp
new file mode 100644
index 0000000..2cf0eb4
--- /dev/null
+++ b/test/math/modPowIterativ.cpp
@@ -0,0 +1,42 @@
+#include "../util.h"
+#include <math/modPowIterativ.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int a = Random::integer<int>(1, 100);
+		int n = Random::integer<int>(2, 100);
+		ll expected = 1;
+		ll k = 0;
+		do {
+			auto got = powMod(a, k, n);
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			k++;
+			expected = (expected * a) % n;
+		} while (k < 100);
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll a = Random::integer<ll>(0, 1'000'000'000);
+		ll b = Random::integer<ll>(0, 1'000'000'000);
+		ll n = Random::integer<ll>(2, 1'000'000'000);
+		t.start();
+		hash += powMod(a, b, n);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/multInv.cpp b/test/math/multInv.cpp
new file mode 100644
index 0000000..93763c5
--- /dev/null
+++ b/test/math/multInv.cpp
@@ -0,0 +1,40 @@
+#include "../util.h"
+#include <math/extendedEuclid.cpp>
+#include <math/multInv.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int i = 0; i < 10'000'000; i++) {
+		ll n = Random::integer<ll>(2, 1'000'000'000);
+		ll x = 0;
+		do {
+			x = Random::integer<ll>(0, n);
+		} while (gcd(x, n) != 1);
+		ll y = multInv(x, n);
+		ll got = (x*y) % n;
+		if (got != 1) cerr << "got: " << got << ", expected: 1" << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll a = Random::integer<ll>(0, 1'000'000'000);
+		ll b = Random::integer<ll>(2, 1'000'000'000);
+		t.start();
+		hash += multInv(a, b);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/permIndex.cpp b/test/math/permIndex.cpp
new file mode 100644
index 0000000..6c77d74
--- /dev/null
+++ b/test/math/permIndex.cpp
@@ -0,0 +1,38 @@
+#include "../util.h"
+#include <math/permIndex.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		vector<ll> cur(n);
+		iota(all(cur), 0);
+		ll expected = 0;
+		do {
+			auto got = permIndex(cur);
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			expected++;
+		} while (expected < 100 && next_permutation(all(cur)));
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 500'000;
+void performance_test() {
+	timer t;
+	vector<ll> cur(N);
+	iota(all(cur), 0);
+	reverse(cur.end() - 10, cur.end());
+	t.start();
+	auto hash = permIndex(cur);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/piLegendre.cpp b/test/math/piLegendre.cpp
new file mode 100644
index 0000000..c3513bf
--- /dev/null
+++ b/test/math/piLegendre.cpp
@@ -0,0 +1,40 @@
+#include "../util.h"
+#include <math/primeSieve.cpp>
+namespace legendre {
+	#include <math/piLegendre.cpp>
+}
+namespace lehmer {
+	#include <math/piLehmer.cpp>
+}
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 1'000; i++) {
+		ll x = Random::integer<ll>(0, 1'000'000'000);
+		auto got = legendre::pi(x);
+		auto expected = lehmer::pi(x);
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int i = 0; i < 1; i++)  {
+		ll x = Random::integer<ll>(0, 1000'000'000'000);
+		t.start();
+		hash += legendre::pi(x);
+		t.stop();
+	}
+	if (t.time > 1500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	lehmer::init();
+	performance_test();
+	stress_test();
+}
+
diff --git a/test/math/piLehmer.cpp b/test/math/piLehmer.cpp
new file mode 100644
index 0000000..d84466f
--- /dev/null
+++ b/test/math/piLehmer.cpp
@@ -0,0 +1,42 @@
+#include "../util.h"
+#include <math/primeSieve.cpp>
+namespace legendre {
+	#include <math/piLegendre.cpp>
+}
+namespace lehmer {
+	#include <math/piLehmer.cpp>
+}
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 1'000; i++) {
+		ll x = Random::integer<ll>(0, 1'000'000'000);
+		auto got = lehmer::pi(x);
+		auto expected = legendre::pi(x);
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	t.start();
+	lehmer::init();
+	t.stop();
+	for (int i = 0; i < 1; i++)  {
+		ll x = Random::integer<ll>(0, 1000'000'000'000);
+		t.start();
+		hash += lehmer::pi(x);
+		t.stop();
+	}
+	if (t.time > 1500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	performance_test();
+	stress_test();
+}
+
diff --git a/test/math/primeSieve.cpp b/test/math/primeSieve.cpp
new file mode 100644
index 0000000..78a50d2
--- /dev/null
+++ b/test/math/primeSieve.cpp
@@ -0,0 +1,47 @@
+#include "../util.h"
+#include <math/primeSieve.cpp>
+
+bool naive(ll x) {
+	for (ll i = 2; i*i <= x; i++) {
+		if (x % i == 0) return false;
+	}
+	return x > 1;
+}
+
+void stress_test() {
+	int queries = 0;
+	vector<ll> found;
+	for (int i = -5; i < 1'000'000; i++) {
+		auto got = isPrime(i);
+		auto expected = naive(i);
+		if (got != expected) cerr << "error: " << i << FAIL;
+		if (got) found.push_back(i);
+		queries++;
+	}
+	primes.resize(sz(found));
+	if (primes != found) cerr << "error: primes" << FAIL;
+	for (int i = 0; i < 1'000'000; i++) {
+		ll x = Random::integer<ll>(2, N);
+		auto got = isPrime(x);
+		auto expected = naive(x);
+		if (got != expected) cerr << "error: " << x << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+void performance_test() {
+	timer t;
+	t.start();
+	primeSieve();
+	hash_t hash = sz(primes);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	performance_test();
+	stress_test();
+}
+
diff --git a/test/math/primitiveRoot.cpp b/test/math/primitiveRoot.cpp
new file mode 100644
index 0000000..cd0b388
--- /dev/null
+++ b/test/math/primitiveRoot.cpp
@@ -0,0 +1,82 @@
+#include "../util.h"
+#define ll lll
+#include <math/modPowIterativ.cpp>
+#undef ll
+#include <math/millerRabin.cpp>
+#include <math/rho.cpp>
+
+ll phi(ll pk, ll p, ll /*k*/) {return pk - pk / p;}
+ll phi(ll n) { // O(sqrt(n))
+	ll res = 1;
+	for (ll p = 2; p * p <= n; p++) {
+		if (n % p == 0) {
+			ll pk = 1;
+			ll k = 0;
+			do {
+				n /= p;
+				pk *= p;
+				k++;
+			} while (n % p == 0);
+			res *= phi(pk, p, k);
+	}}
+	if (n > 1) res *= phi(n, n, 1);
+	return res;
+}
+
+#include <math/primitiveRoot.cpp>
+
+bool naiveIsPrimitive(ll g, ll n) {
+	if (gcd(g, n) != 1) return false;
+	vector<bool> seen(n);
+	ll c = g;
+	for (ll i = 0; i < n; i++) {
+		seen[c] = true;
+		c = (c * g) % n;
+	}
+	ll res = 0;
+	for (bool x : seen) if (x) res++;
+	return res == phi(n);
+}
+
+void stress_test() {
+	int queries = 0;
+	for (int tries = 0; tries < 20'000; tries++) {
+		ll a = Random::integer<ll>(1, 3);
+		ll p = Random::prime<ll>(0, 1000);
+		ll k = p == 2 ? 1 : Random::integer<ll>(1, log(100'000) / log(p) + 1);
+
+		ll x = a;
+		for (int i = 0; i < k; i++) x *= p;
+
+		ll got = findPrimitive(x);
+
+		if (got < 0 || got >= x) cerr << "error: out of range" << FAIL;
+		if (!naiveIsPrimitive(got, x)) cerr << "error: wrong" << got << " " << x << FAIL;
+		queries++;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+void stress_test2() {
+	int queries = 0;
+	for (int x = 2; x < 5'000; x++) {
+		map<ll, int> facts;
+		factor(x, facts);
+		if (x % 2 == 0) facts.erase(facts.find(2));
+		bool expected = sz(facts) == 1;
+		if (x % 4 == 0) expected = false;
+		if (x == 2 || x == 4) expected = true;
+
+		bool got = findPrimitive(x) >= 0;
+
+		if (got != expected) cerr << "error" << FAIL;
+		queries++;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+	stress_test2();
+}
+
diff --git a/test/math/rho.cpp b/test/math/rho.cpp
new file mode 100644
index 0000000..5e4792a
--- /dev/null
+++ b/test/math/rho.cpp
@@ -0,0 +1,117 @@
+#include "../util.h"
+#define ll lll
+#include <math/modPowIterativ.cpp>
+#undef ll
+#include <math/millerRabin.cpp>
+#include <math/rho.cpp>
+
+map<ll, int> factor(ll n) {
+	map<ll, int> facts;
+	factor(n, facts);
+	return facts;
+}
+
+ll mul(const map<ll, int>& facts) {
+	ll res = 1;
+	for (auto [p, c] : facts) {
+		for (int i = 0; i < c; i++) res *= p;
+	}
+	if (res < 1 || res > (1ll << 62)) cerr << "invalid number: " << res << FAIL;
+	return res;
+}
+
+void stress_test() {
+	vector<map<ll, int>> test = {
+		{}, // 1
+		{{2, 1}},
+		{{3, 1}},
+		{{2, 2}},
+		{{5, 1}},
+		{{2, 1}, {3, 1}},
+		{{2, 2}, {3, 1}},
+		{{2, 1}, {3, 2}},
+		{{2, 2}, {3, 2}},
+		{{2, 62}},
+		{{2, 18}, {5, 18}},
+		{{352523, 1}, {352817, 1}},
+		{{41, 1}, {71, 1}, {421, 1}, {811, 1}},
+		{{11, 1}, {17, 1}, {31, 1}, {61, 1}, {73, 1}, {66361, 1}},
+		{{500000003, 1}, {1999999973, 1}},
+		{{65537, 2}},
+		{{999665081, 1}, {999716071, 1}},
+		{{550177, 1}, {1100353, 1}, {1650529, 1}},
+		{{459397, 1}, {918793, 1}, {1378189, 1}},
+		{{37, 1}, {109, 1}},
+		{{31, 1}, {151, 1}},
+		{{239, 1}, {1429, 1}},
+		{{89, 1}, {1093, 1}},
+		{{2, 3}, {15800133918749317, 1}},
+		{{12251, 1}, {85751, 1}},
+		{{3, 1}, {5, 3}, {131, 1}, {6855593, 1}},
+		{{5, 1}, {1927962474784631, 1}},
+		{{197279, 1}, {1775503, 1}},
+		{{3716371, 1}, {14865481, 1}},
+		{{3, 1}, {5, 1}, {3075593, 1}, {3075593, 1}},
+		{{4880401, 1}, {9760801, 1}},
+		{{2822159, 1}, {11288633, 1}},
+		{{3290341, 1}, {6580681, 1}},
+		{{611557, 1}, {1834669, 1}},
+		{{9227, 1}, {894923, 1}, {968731, 1}},
+		{{3, 4}, {13, 1}, {62633, 2}},
+		{{2, 2}, {3, 1}, {5, 1}, {167, 2}, {299197, 2}},
+		{{332721269, 1}, {560937673, 1}},
+		{{30702523, 1}, {122810089, 1}},
+		{{24786439, 1}, {123932191, 1}},
+		{{382500329, 1}, {1530001313, 1}},
+		{{2, 4}, {5, 4}, {13, 1}, {30839, 2}},
+		{{3, 1}, {385417, 1}, {7985344259, 1}},
+		{{2, 4}, {3, 1}, {5, 1}, {7, 2}, {61, 1}, {179, 2}, {1381, 2}},
+		{{627838711, 1}, {1212379867, 1}},
+		{{3, 5}, {5, 3}, {41, 2}, {157321, 2}},
+		{{5, 2}, {13, 1}},
+		{{3, 1}, {5, 5}},
+		{{2, 1}, {73, 1}, {193, 1}},
+		{{5, 2}, {13, 1}, {19, 1}, {73, 1}},
+		{{2, 3}, {3, 1}, {407521, 1}},
+		{{2, 1}, {3, 1}, {299210837, 1}},
+		{{2, 8}, {3, 4}, {5, 2}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}, {23, 1}, {29, 1}, {3137, 1}},
+	};
+
+	timer t;
+	for (auto expected : test) {
+		ll x = mul(expected);
+		t.start();
+		auto got = factor(x);
+		t.stop();
+		if (got != expected) {
+			cerr << "number: " << x << endl;
+			cerr << "got:" << endl;
+			for (auto [p, c] : got) cerr << p << "^" << c << endl;
+			cerr << "expected" << endl;
+			for (auto [p, c] : expected) cerr << p << "^" << c << endl;
+			cerr << FAIL;
+		}
+	}
+	if (t.time > 100) cerr << "too slow" << FAIL;
+	cerr << "stress tested: " << t.time << "ms" << endl;
+}
+
+constexpr int N = 2'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll x = Random::integer<ll>(1e18 / 2, 1e18);
+		t.start();
+		hash += factor(x).size();
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/shortModInv.cpp b/test/math/shortModInv.cpp
new file mode 100644
index 0000000..26960bf
--- /dev/null
+++ b/test/math/shortModInv.cpp
@@ -0,0 +1,39 @@
+#include "../util.h"
+#include <math/shortModInv.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int i = 0; i < 10'000'000; i++) {
+		ll n = Random::integer<ll>(2, 1'000'000'000);
+		ll x = 0;
+		do {
+			x = Random::integer<ll>(0, n);
+		} while (gcd(x, n) != 1);
+		ll y = multInv(x, n);
+		ll got = (x*y) % n;
+		if (got != 1) cerr << "got: " << got << ", expected: 1" << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll a = Random::integer<ll>(0, 1'000'000'000);
+		ll b = Random::integer<ll>(2, 1'000'000'000);
+		t.start();
+		hash += multInv(a, b);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/simpson.cpp b/test/math/simpson.cpp
new file mode 100644
index 0000000..d7cdba3
--- /dev/null
+++ b/test/math/simpson.cpp
@@ -0,0 +1,63 @@
+#include "../util.h"
+std::function<double(double)> f;
+constexpr double EPS = 1e-9;
+#include <math/simpson.cpp>
+
+struct RandomPolynom {
+	vector<double> polynom;
+	RandomPolynom(int deg) : polynom(deg) {
+		for (auto& x : polynom) x = Random::real<double>(-100, 100);
+	}
+	double operator()(double x) const {
+		double res = 0;
+		double xx = 1;
+		for (double y : polynom ) {
+			res += xx * y;
+			xx *= x;
+		}
+		return res;
+	}
+	double area(double a, double b) const {
+		double res = 0;
+		double aa = a;
+		double bb = b;
+		ll d = 1;
+		for (double y : polynom) {
+			res += bb / d * y;
+			res -= aa / d * y;
+			aa *= a;
+			bb *= b;
+			d++;
+		}
+		return res;
+	}
+};
+
+void stress_test() {
+	timer t;
+	ll queries = 0;
+	for (int tries = 0; tries < 1'000; tries++) {
+		ll n = Random::integer<ll>(0, 6);
+		RandomPolynom poly(n);
+		f = poly;
+		for (ll i = 0; i < 200; i++) {
+			double l = Random::real<double>(-20, 20);
+			double r = Random::real<double>(-20, 20);
+			if (l > r) swap(l, r);
+
+			t.start();
+			double got = integrate(l, r);
+			t.stop();
+			double expected = poly.area(l, r);
+			if (float_error(got, expected) > 1e-6) cerr << fixed << setprecision(20) << "got: " << got << ", expected: " << expected << FAIL;
+			queries++;
+		}
+	}
+	if (t.time > 5000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested random queries: " << queries << " (" << t.time << "ms)" << endl;
+}
+
+int main() {
+	stress_test();
+}
+
diff --git a/test/math/sqrtModCipolla.cpp b/test/math/sqrtModCipolla.cpp
new file mode 100644
index 0000000..26d975b
--- /dev/null
+++ b/test/math/sqrtModCipolla.cpp
@@ -0,0 +1,48 @@
+#include "../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/legendre.cpp>
+mt19937 rng(123456789);
+#include <math/sqrtModCipolla.cpp>
+
+void stress_test(ll range) {
+	ll work = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		ll p = Random::prime<ll>(range);
+		for (ll j = 0; j < 100; j++) {
+			ll x = Random::integer<ll>(0, p);
+			if (legendre(x, p) < 0) continue;
+
+			ll got = sqrtMod(x, p);
+			if (got < 0 || got >= p) cerr << "error: out of range" << FAIL;
+			if ((got * got) % p != x) cerr << "error: not root" << FAIL;
+			work++;
+		}
+	}
+	cerr << "stress tested: " << work << endl;
+}
+
+constexpr int N = 200'000;
+constexpr ll mod = 1'394'633'899;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll x;
+		do {
+			x = Random::integer<ll>(0, mod);
+		} while (legendre(x, mod) >= 0);
+		t.start();
+		hash += sqrtMod(x, mod);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+
+int main() {
+	stress_test(1'000);
+	stress_test(1'000'000'000);
+	performance_test();
+}
+
diff --git a/test/math/transforms/andTransform.cpp b/test/math/transforms/andTransform.cpp
new file mode 100644
index 0000000..fa029f6
--- /dev/null
+++ b/test/math/transforms/andTransform.cpp
@@ -0,0 +1,38 @@
+#include "../../util.h"
+#include <math/transforms/andTransform.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = 1ll << Random::integer<int>(0, 10);
+		auto expected = Random::integers<ll>(n, -1000, 1000);
+		auto got = expected;
+		fft(got, false);
+		fft(got, true);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 23;
+void performance_test() {
+	timer t;
+	vector<ll> a = Random::integers<ll>(N, -1000, 1000);
+	vector<ll> b = Random::integers<ll>(N, -1000, 1000);
+	t.start();
+	fft(a, true);
+	fft(b, false);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * a[i];
+	for (ll i = 0; i < N; i++) hash += i * b[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/transforms/bitwiseTransforms.cpp b/test/math/transforms/bitwiseTransforms.cpp
new file mode 100644
index 0000000..132740c
--- /dev/null
+++ b/test/math/transforms/bitwiseTransforms.cpp
@@ -0,0 +1,38 @@
+#include "../../util.h"
+#include <math/transforms/bitwiseTransforms.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = 1ll << Random::integer<int>(0, 10);
+		auto expected = Random::integers<ll>(n, -1000, 1000);
+		auto got = expected;
+		bitwiseConv(got, false);
+		bitwiseConv(got, true);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 23;
+void performance_test() {
+	timer t;
+	vector<ll> a = Random::integers<ll>(N, -1000, 1000);
+	vector<ll> b = Random::integers<ll>(N, -1000, 1000);
+	t.start();
+	bitwiseConv(a, true);
+	bitwiseConv(b, false);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * a[i];
+	for (ll i = 0; i < N; i++) hash += i * b[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/transforms/fft.cpp b/test/math/transforms/fft.cpp
new file mode 100644
index 0000000..858676b
--- /dev/null
+++ b/test/math/transforms/fft.cpp
@@ -0,0 +1,51 @@
+#include "../../util.h"
+#include <math/transforms/fft.cpp>
+
+vector<cplx> to_cplx(const vector<ll>& in) {
+	vector<cplx> res(sz(in));
+	for (int i = 0; i < sz(in); i++) res[i] = in[i];
+	return res;
+}
+
+vector<ll> from_cplx(const vector<cplx>& in) {
+	vector<ll> res(sz(in));
+	for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i]));
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = 1ll << Random::integer<int>(0, 10);
+		auto expected = Random::integers<ll>(n, -1000, 1000);
+		vector<cplx> tmp = to_cplx(expected);
+		fft(tmp, false);
+		fft(tmp, true);
+		auto got = from_cplx(tmp);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 21;
+void performance_test() {
+	timer t;
+	auto a = to_cplx(Random::integers<ll>(N, -1000, 1000));
+	auto b = to_cplx(Random::integers<ll>(N, -1000, 1000));
+	t.start();
+	fft(a, true);
+	fft(b, false);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * llround(real(a[i]));
+	for (ll i = 0; i < N; i++) hash += i * llround(real(b[i]));
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/transforms/fftMul.cpp b/test/math/transforms/fftMul.cpp
new file mode 100644
index 0000000..5933864
--- /dev/null
+++ b/test/math/transforms/fftMul.cpp
@@ -0,0 +1,62 @@
+#include "../../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/fft.cpp>
+#pragma GCC diagnostic ignored "-Wnarrowing"
+#include <math/transforms/fftMul.cpp>
+
+vector<ll> from_cplx(const vector<cplx>& in) {
+	vector<ll> res(sz(in));
+	for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i]));
+	return res;
+}
+
+vector<ll> naive(const vector<ll>& a, const vector<ll>& b) {
+	vector<ll> res;
+	for (ll i = 1;; i *= 2) {
+		if (sz(a) + sz(b) <= i) {
+			res.resize(i, 0);
+			break;
+		}
+	}
+	for (int i = 0; i < sz(a); i++) {
+		for (int j = 0; j < sz(b); j++) {
+			res[i+j] += a[i] * b[j];
+		}
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		auto a = Random::integers<ll>(n, -1000, 1000);
+		auto b = Random::integers<ll>(m, -1000, 1000);
+		auto expected = naive(a, b);
+		auto got = from_cplx(mul(a, b));
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 20;
+void performance_test() {
+	timer t;
+	vector<ll> a = Random::integers<ll>(N, -1000, 1000);
+	vector<ll> b = Random::integers<ll>(N, -1000, 1000);
+	t.start();
+	auto got = from_cplx(mul(a, b));
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * got[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/transforms/multiplyBitwise.cpp b/test/math/transforms/multiplyBitwise.cpp
new file mode 100644
index 0000000..bc73290
--- /dev/null
+++ b/test/math/transforms/multiplyBitwise.cpp
@@ -0,0 +1,55 @@
+#include "../../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/bitwiseTransforms.cpp>
+#include <math/transforms/multiplyBitwise.cpp>
+
+vector<ll> naive(const vector<ll>& a, const vector<ll>& b) {
+	vector<ll> res;
+	for (ll i = 1;; i *= 2) {
+		if (sz(a) <= i && sz(b) <= i) {
+			res.resize(i, 0);
+			break;
+		}
+	}
+	for (int i = 0; i < sz(a); i++) {
+		for (int j = 0; j < sz(b); j++) {
+			res[i&j] += a[i] * b[j];
+		}
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		auto a = Random::integers<ll>(n, -1000, 1000);
+		auto b = Random::integers<ll>(m, -1000, 1000);
+		auto expected = naive(a, b);
+		auto got = mul(a, b);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 22;
+void performance_test() {
+	timer t;
+	vector<ll> a = Random::integers<ll>(N, -1000, 1000);
+	vector<ll> b = Random::integers<ll>(N, -1000, 1000);
+	t.start();
+	auto got = mul(a, b);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * got[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/transforms/multiplyFFT.cpp b/test/math/transforms/multiplyFFT.cpp
new file mode 100644
index 0000000..782be1b
--- /dev/null
+++ b/test/math/transforms/multiplyFFT.cpp
@@ -0,0 +1,55 @@
+#include "../../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/fft.cpp>
+#include <math/transforms/multiplyFFT.cpp>
+
+vector<ll> naive(const vector<ll>& a, const vector<ll>& b) {
+	vector<ll> res;
+	for (ll i = 1;; i *= 2) {
+		if (sz(a) + sz(b) <= i) {
+			res.resize(i, 0);
+			break;
+		}
+	}
+	for (int i = 0; i < sz(a); i++) {
+		for (int j = 0; j < sz(b); j++) {
+			res[i+j] += a[i] * b[j];
+		}
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		auto a = Random::integers<ll>(n, -1000, 1000);
+		auto b = Random::integers<ll>(m, -1000, 1000);
+		auto expected = naive(a, b);
+		auto got = mul(a, b);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 19;
+void performance_test() {
+	timer t;
+	vector<ll> a = Random::integers<ll>(N, -1000, 1000);
+	vector<ll> b = Random::integers<ll>(N, -1000, 1000);
+	t.start();
+	auto got = mul(a, b);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * got[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/transforms/multiplyNTT.cpp b/test/math/transforms/multiplyNTT.cpp
new file mode 100644
index 0000000..70fc137
--- /dev/null
+++ b/test/math/transforms/multiplyNTT.cpp
@@ -0,0 +1,56 @@
+#include "../../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/ntt.cpp>
+#include <math/transforms/multiplyNTT.cpp>
+
+vector<ll> naive(const vector<ll>& a, const vector<ll>& b) {
+	vector<ll> res;
+	for (ll i = 1;; i *= 2) {
+		if (sz(a) + sz(b) <= i) {
+			res.resize(i, 0);
+			break;
+		}
+	}
+	for (int i = 0; i < sz(a); i++) {
+		for (int j = 0; j < sz(b); j++) {
+			res[i+j] += a[i] * b[j];
+			res[i+j] %= mod;
+		}
+	}
+	return res;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		auto a = Random::integers<ll>(n, 0, mod);
+		auto b = Random::integers<ll>(m, 0, mod);
+		auto expected = naive(a, b);
+		auto got = mul(a, b);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 20;
+void performance_test() {
+	timer t;
+	vector<ll> a = Random::integers<ll>(N, 0, mod);
+	vector<ll> b = Random::integers<ll>(N, 0, mod);
+	t.start();
+	auto got = mul(a, b);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * got[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/transforms/ntt.cpp b/test/math/transforms/ntt.cpp
new file mode 100644
index 0000000..cd32073
--- /dev/null
+++ b/test/math/transforms/ntt.cpp
@@ -0,0 +1,39 @@
+#include "../../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/ntt.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = 1ll << Random::integer<int>(0, 10);
+		auto expected = Random::integers<ll>(n, 0, mod);
+		auto got = expected;
+		ntt(got, false);
+		ntt(got, true);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 22;
+void performance_test() {
+	timer t;
+	vector<ll> a = Random::integers<ll>(N, 0, mod);
+	vector<ll> b = Random::integers<ll>(N, 0, mod);
+	t.start();
+	ntt(a, true);
+	ntt(b, false);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * a[i];
+	for (ll i = 0; i < N; i++) hash += i * b[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/transforms/orTransform.cpp b/test/math/transforms/orTransform.cpp
new file mode 100644
index 0000000..0ec9155
--- /dev/null
+++ b/test/math/transforms/orTransform.cpp
@@ -0,0 +1,38 @@
+#include "../../util.h"
+#include <math/transforms/orTransform.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = 1ll << Random::integer<int>(0, 10);
+		auto expected = Random::integers<ll>(n, -1000, 1000);
+		auto got = expected;
+		fft(got, false);
+		fft(got, true);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 23;
+void performance_test() {
+	timer t;
+	vector<ll> a = Random::integers<ll>(N, -1000, 1000);
+	vector<ll> b = Random::integers<ll>(N, -1000, 1000);
+	t.start();
+	fft(a, true);
+	fft(b, false);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * a[i];
+	for (ll i = 0; i < N; i++) hash += i * b[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/transforms/xorTransform.cpp b/test/math/transforms/xorTransform.cpp
new file mode 100644
index 0000000..17b0f6f
--- /dev/null
+++ b/test/math/transforms/xorTransform.cpp
@@ -0,0 +1,38 @@
+#include "../../util.h"
+#include <math/transforms/xorTransform.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = 1ll << Random::integer<int>(0, 10);
+		auto expected = Random::integers<ll>(n, -1000, 1000);
+		auto got = expected;
+		fft(got, false);
+		fft(got, true);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1ll << 23;
+void performance_test() {
+	timer t;
+	vector<ll> a = Random::integers<ll>(N, -1000, 1000);
+	vector<ll> b = Random::integers<ll>(N, -1000, 1000);
+	t.start();
+	fft(a, true);
+	fft(b, false);
+	t.stop();
+	hash_t hash = 0;
+	for (ll i = 0; i < N; i++) hash += i * a[i];
+	for (ll i = 0; i < N; i++) hash += i * b[i];
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+