Adding primitive root and discrete logarithm.

3 files changed, 54 insertions, 0 deletions

diff --git a/math/discreteLogarithm.cpp b/math/discreteLogarithm.cpp
new file mode 100644
index 0000000..6d3f656
--- /dev/null
+++ b/math/discreteLogarithm.cpp
@@ -0,0 +1,13 @@
+// Bestimmt Lösung x für a^x=b mod m.
+ll solve (ll a, ll b, ll m) { // Laufzeit: O(sqrt(m)*log(m))
+  ll n = (ll)sqrt((double)m) + 1;
+  map<ll,ll> vals;
+  for (int i = n; i >= 1; i--) vals[powMod(a, i * n, m)] = i;
+  for (int i = 0; i <= n; i++) {
+    ll cur = (powMod(a, i, m) * b) % m;
+    if (vals.count(cur)) {
+      ll ans = vals[cur] * n - i;
+      if (ans < m) return ans;
+  }}
+  return -1;
+}
diff --git a/math/math.tex b/math/math.tex
index ba94b18..a27c992 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -73,6 +73,24 @@ Vorberechnen, wenn häufig benötigt.
 \end{itemize}
 \lstinputlisting{math/phi.cpp}
 
+\subsection{Primitivwurzeln}
+\begin{itemize}[nosep]
+	\item Primitivwurzel modulo $n$ existiert genau dann wenn:
+	\begin{itemize}[nosep]
+		\item $n$ ist $1$, $2$ oder $4$, oder
+		\item $n$ ist Potenz einer ungeraden Primzahl, oder
+		\item $n$ ist das Doppelte einer Potenz einer ungeraden Primzahl.
+	\end{itemize}
+
+	\item Sei $g$ Primitivwurzel modulo $n$.
+	Dann gilt:\newline
+	Das kleinste $k$, sodass $g^k \equiv 1 \mod n$, ist $k = \varphi(n)$.
+\end{itemize}
+\lstinputlisting{math/primitiveRoot.cpp}
+
+\subsection{Diskreter Logarithmus}
+\lstinputlisting{math/discreteLogarithm.cpp}
+
 \subsection{Polynome \& FFT}
 Multipliziert Polynome $A$ und $B$.
 \begin{itemize}[nosep]
diff --git a/math/primitiveRoot.cpp b/math/primitiveRoot.cpp
new file mode 100644
index 0000000..3ad828d
--- /dev/null
+++ b/math/primitiveRoot.cpp
@@ -0,0 +1,23 @@
+// Ist g Primitivwurzel modulo p. Teste zufällige g, um eine zu finden.
+bool is_primitive(ll g, ll p) {
+  map<ll, int> facs;
+  factor(p - 1, facs);
+  for (auto &f : facs)
+    if (1 == powMod(g, (p - 1) / f.first, p)) 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<ll, int> 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;
+}