diff options
Diffstat (limited to 'math')
| -rw-r--r-- | math/math.tex | 1 | ||||
| -rw-r--r-- | math/rho.cpp | 14 |
2 files changed, 9 insertions, 6 deletions
diff --git a/math/math.tex b/math/math.tex index fe288dc..d637e0c 100644 --- a/math/math.tex +++ b/math/math.tex @@ -146,6 +146,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{itemize} \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2} \sourcecode{math/millerRabin.cpp} + \columnbreak \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}3]{n}} \sourcecode{math/rho.cpp} \method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}} diff --git a/math/rho.cpp b/math/rho.cpp index 4579a01..2a64d3c 100644 --- a/math/rho.cpp +++ b/math/rho.cpp @@ -1,13 +1,15 @@ +using lll = __int128; 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) { + ll x = 0, y = 0; + lll 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++) { + if (x == y) x = ++i, y = f(x); + if (lll q = prd * abs(x-y) % n; q) prd = q; x = f(x); y = f(f(y)); - d = gcd(abs(x - y), n); } - return d == n ? rho(n) : d; + return mgcd(prd, n); } void factor(ll n, map<ll, int>& facts) { |