From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- math/rho.cpp | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100644 math/rho.cpp (limited to 'math/rho.cpp') 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& facts) { + if (n == 1) return; + if (isPrime(n)) { + facts[n]++; + return; + } + ll f = rho(n); + factor(n / f, facts); + factor(f, facts); +} -- cgit v1.2.3