From 8cb8cc9041e73c082483ddb7edc94da0bbe5efb8 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 22 Jan 2023 23:41:29 +0100 Subject: improved pollard -rho --- math/math.tex | 1 + math/rho.cpp | 14 ++++++++------ 2 files changed, 9 insertions(+), 6 deletions(-) (limited to 'math') 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& facts) { -- cgit v1.2.3