1 files changed, 22 insertions, 0 deletions
diff --git a/math/rho.cpp b/math/rho.cpp
new file mode 100644
index 0000000..bd30902
--- /dev/null
+++ b/math/rho.cpp
@@ -0,0 +1,22 @@
+ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim.
+	if (n % 2 == 0) return 2;
+	ll c = rand() % n, x = rand() % n, y = x, d = 1;
+														 // mulmod or int128
+	auto f = [&](ll x){return ((x * x) % n + c) % n;};
+	while (d == 1) {
+		x = f(x); y = f(f(y));
+		d = gcd(abs(x - y), n);
+	}
+	return d == n ? rho(n) : d;
+}
+
+void factor(ll n, map<ll, int>& facts) {
+	if (n == 1) return;
+	if (isPrime(n)) {
+		facts[n]++;
+		return;
+	}
+	ll f = rho(n);
+	factor(n / f, facts);
+	factor(f, facts);
+}