diff options
| author | Noobie99 <noob999noob999@gmail.com> | 2023-02-01 15:28:48 +0100 |
|---|---|---|
| committer | Noobie99 <noob999noob999@gmail.com> | 2023-02-01 15:28:48 +0100 |
| commit | 297da53061153d8d092e4279aec4b51744071e2f (patch) | |
| tree | ea0c2a5c2df047dc37de10527cb7c2a0b581f7f4 /math/rho.cpp | |
| parent | dca70f3ff8aa6e0a7b2a9ceb06d8b7f1f8d550c2 (diff) | |
fixed rho
Diffstat (limited to 'math/rho.cpp')
| -rw-r--r-- | math/rho.cpp | 9 |
1 files changed, 4 insertions, 5 deletions
diff --git a/math/rho.cpp b/math/rho.cpp index 2a64d3c..1f5ba86 100644 --- a/math/rho.cpp +++ b/math/rho.cpp @@ -1,15 +1,14 @@ using lll = __int128; ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim. if (n % 2 == 0) return 2; - ll x = 0, y = 0; - lll prd = 2; + ll x = 0, y = 0, prd = 2; auto f = [n](lll x){return (x * x) % n + 1;}; - for (ll t = 30, i = n / 2 + 7; t % 40 || mgcd(prd, n) == 1; t++) { + for (ll t = 30, i = n / 2 + 7; t % 40 || gcd(prd, n) == 1; t++) { if (x == y) x = ++i, y = f(x); - if (lll q = prd * abs(x-y) % n; q) prd = q; + if (ll q = (lll)prd * abs(x-y) % n; q) prd = q; x = f(x); y = f(f(y)); } - return mgcd(prd, n); + return gcd(prd, n); } void factor(ll n, map<ll, int>& facts) { |