From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- math/primitiveRoot.cpp | 40 ++++++++++++++++++++-------------------- 1 file changed, 20 insertions(+), 20 deletions(-) (limited to 'math/primitiveRoot.cpp') diff --git a/math/primitiveRoot.cpp b/math/primitiveRoot.cpp index 3ad828d..36a9367 100644 --- a/math/primitiveRoot.cpp +++ b/math/primitiveRoot.cpp @@ -1,23 +1,23 @@ -// Ist g Primitivwurzel modulo p. Teste zufällige g, um eine zu finden. -bool is_primitive(ll g, ll p) { - map facs; - factor(p - 1, facs); - for (auto &f : facs) - if (1 == powMod(g, (p - 1) / f.first, p)) return false; - return true; +bool isPrimitive(ll g, ll n, ll phi, map phiFacs) { + if (g == 1) return n == 2; + for (auto& f : phiFacs) + if (1 == powMod(g, phi / f.first, n)) return false; + return true; } -// Alternativ: Generator zum Finden. -1 falls keine existiert. -ll generator (ll p) { // Laufzeit: O(ans*log(phi(n))*log(n)) - map facs; - factor(n, facs); - ll phi = phi(p), n = phi; - - for (ll res = 2; res <= p; res++) { - bool ok = true; - for (auto &f : facs) - ok &= powMod(res, phi / f.first, p) != 1; - if (ok) return res; - } - return -1; +bool isPrimitive(ll g, ll n) { + ll phin = phi(n); //isPrime(n) => phi(n) = n - 1 + map phiFacs; + factor(phin, phiFacs); + return isPrimitive(g, n, phin, phiFacs); } + +ll findPrimitive(ll n) { + ll phin = phi(n); //isPrime(n) => phi(n) = n - 1 + map phiFacs; + factor(phin, phiFacs); + //auch zufällige Reihenfolge möglich! + for (ll res = 1; res < n; res++) + if (isPrimitive(res, n, phin, phiFacs)) return res; + return -1; +} \ No newline at end of file -- cgit v1.2.3