163 lines
9.2 KiB
TeX
163 lines
9.2 KiB
TeX
\chapter{Modulare Arithmetik - Teil 2}
|
|
\section{Potenzen}
|
|
Potenzen sind für beliebige Zahlen $a\in\mathbb{Z}_n$ für natürliche Exponenten $i\in\mathbb{N}$ wie üblich definiert:
|
|
$$a^i:=\underbrace{a\cdot a\cdots a}_i$$
|
|
Ist $a$ invertierbar ($a\in\mathbb{Z}_n^*$) so sind die Potenzen für alle ganzzahligen Exponenten $i\in\mathbb{Z}$ definiert,
|
|
indem $a^0 = 1$ und $a^{-i}:=(a^{-1})^i$ definiert werden.
|
|
Folglich gelten die Folgenden Regeln:
|
|
\begin{mybox}
|
|
für $a,b\in\mathbb{Z}_n$ und $i,j\in \mathbb{N}$ oder für $a,b\in\mathbb{Z}_n^*$ und $i,j\in\mathbb{Z}$ gilt:
|
|
$$\begin{aligned}
|
|
a^i\cdot a^j &= a^{i+j}\\
|
|
(a^i)^j &= a^{ij}\\
|
|
a^i\cdot b^i &= (ab)^i\\
|
|
\end{aligned}$$
|
|
\end{mybox}
|
|
|
|
\subsection{Erzeugnis und Ordnung eines invertierbaren Elements}
|
|
Die zyklische Untergruppe, die aus den Potenzen eines Elementes $a\in\mathbb{Z}_n^*$ entsteht wird als Erzeugnis von $a$ in $\mathbb{Z}_n^*$ bezeichnet.
|
|
$$<a>:=\{a^i\mid i\in\mathbb{Z}\}$$
|
|
Die Anzahl der verschiedenen Potenzen von $a$ wird als Ordnung von $a$ in $\mathbb{Z}_n^*$ bezeichnet:
|
|
$$o_n(a):=|<a>|$$
|
|
Hierbei ergibt sich $a^{o(a)}=1$ und $<a>=\{1,a,a^2,a^3,...,a^{o(a)-1}\}$.\\
|
|
\begin{mybox}
|
|
für $n\in\mathbb{N}(n\ge 2);a,b\in \mathbb{Z}_n^*$ und $i\in\mathbb{Z}$ gilt:
|
|
\begin{enumerate}[(i)]
|
|
\item $a^i=1 \Longrightarrow o(a)|i$
|
|
\item $o(a^i)|o(a)$
|
|
\item $i|o(a) \Longrightarrow o(a^i)=\frac{o(a)}{|i|}$
|
|
\item $\text{ggT}(o(a),i)=1 \Longrightarrow o(a^i)=o(a)$
|
|
\item $o(ab)|o(a)\cdot o(b)$
|
|
\item $\text{ggT}(o(a),o(b))=1\Longrightarrow o(a\cdot b)=o(a)\cdot o(b)$
|
|
\end{enumerate}
|
|
\end{mybox}
|
|
\begin{mybox}
|
|
Wenn $\mu_n$ für $n\in\mathbb{N},n\ge2$ die maximale Ordnung eines Elementes aus $\mathbb{Z}_n^*$ ($\mu_n:=\max\{o(a)\mid a\in\mathbb{Z}_n^*\}$),
|
|
ist jede Ordnung von $a$ ein Teiler von $\mu_n$
|
|
\end{mybox}
|
|
|
|
\subsection{Faktorenzerlegung}
|
|
Falls es für ein Polynom $p(x) \in \mathbb{Z}_n[x]$ ($n\in\mathbb{N}$) vom Grad $k$ eine Nullstelle $a\in\mathbb{Z}_n$ gibt,
|
|
muss es ein Polynom $q(x) \in \mathbb{Z}_n[x]$ vom Grad $k-1$ geben, für das gilt:
|
|
$$p(x)=(x-a)\cdot q(x)$$
|
|
|
|
\subsection{Kleiner Satz von Fermat}
|
|
Für eine Primzahl $p$ gilt für alle $a\in\mathbb{Z}$ mit $\text{ggT}(a,p)=1$:
|
|
$$a^{p-1}\equiv 1 \hspace{10mm}(\mod p)$$
|
|
|
|
\subsection{Berechnung modularer Potenzen}
|
|
Es gibt zwei verschiedene Varianten zur effizienten Berechnung modularer Potenzen, die sich beide an der Darstellung des Exponenten $e$ im Stellenwertsystem zur Basis 2 (binär) orientieren:
|
|
Es lässt sich ein Algorithmus aufstellen, bei dem sukzessive die Quadrate $a^2,a^4=(a^2)^2, a^8=(a^4)^2,...,a^{2^l-1}=\left(a^{2^{l-2}}\right)^2$ in $\mathbb{Z}_n$ berechnet werden.
|
|
Diese fließen als Faktor in die Berechnung von $p=a^e$ ein, falls das entsprechende Bit $e_i=1$ ist.
|
|
Es folgen die beiden Algorithmen:
|
|
\begin{mybox}
|
|
\textbf{Algorithmus 1}\\
|
|
Sei $n\in\mathbb{N},a\in\mathbb{Z}_n$ und $e\in\mathbb{N}$ (in binärer Schreibweise):
|
|
$$e=(e_{l-1}...e_2 e_1 e_0)_2=\sum_{i=0}^{l-1}e_i\cdot 2^i$$
|
|
Für die Berechnung von $p=a^e\mod n$ wird der folgende Algorithmus angewandt:
|
|
\begin{enumerate}[(1)]
|
|
\item $i:=0,p:=1$ und $s:=a$
|
|
\item if($e_i=1$){$p:=p\cdot s\mod n$}
|
|
\item if($i=l-1$){beende den Algorithmus und gebe $p$ aus}
|
|
\item $i:=i+1$
|
|
\item $s:=s^2\mod n$
|
|
\item goto (2)
|
|
\end{enumerate}
|
|
\end{mybox}
|
|
\begin{mybox}
|
|
\textbf{Algorithmus 2}\\
|
|
Sei $n\in\mathbb{N},a\in\mathbb{Z}_n$ und $e\in\mathbb{N}$ (in binärer Schreibweise):
|
|
$$e=(e_{l-1}...e_2 e_1 e_0)_2=\sum_{i=0}^{l-1}e_i\cdot 2^i$$
|
|
Für die Berechnung von $p=a^e\mod n$ wird der folgende Algorithmus angewandt:
|
|
\begin{enumerate}[(1)]
|
|
\item $i:=l-1,p:=1$ und $s:=a$
|
|
\item if($e_i=1$){$p:=p\cdot a\mod n$}
|
|
\item if($i=0$){beende den Algorithmus und gebe $p$ aus}
|
|
\item $i:=i-1$
|
|
\item $p:=p^2\mod n$
|
|
\item goto (2)
|
|
\end{enumerate}
|
|
\end{mybox}
|
|
|
|
|
|
\section{Exkurs: Einheitengruppe $\mathbb{Z}_{p^e}^*$}
|
|
Für eine Primzahl $p$ gibt es ein Element $g\in\mathbb{Z}_p^*$ mit $o(g)=p-1$ ($\mathbb{Z}_p^*=<g>=\{1,g,g^2,...,g^{p-2}\}$).
|
|
Diese Elemente $g$ werden als \textbf{primitive Elemente} bezeichnet.\\
|
|
Mithilfe der Potenzen der primitiven Elemente lassen sich alle Elemente von $\mathbb{Z}_p^*$ generieren:
|
|
$$<g>=\mathbb{Z}_p^*$$
|
|
Diese Elemente werden daher auch als \textbf{Generatoren} von $\mathbb{Z}_p^*$ bezeichnet.
|
|
Auch für Einheitengruppen $\mathbb{Z}_{p^e}$ für Primzahlpotenzen mit $e>1$ gibt es solche zyklische Generatoren:
|
|
\begin{mybox}
|
|
für eine Primzahl $p\ne2$ und $e\in\mathbb{N}$ gibt es ein $g\in\mathbb{Z}_{p^e}^*$ für das gilt:
|
|
$$\begin{aligned}
|
|
o(g)=p^{e-1}(p-1) &= \varphi(p^e)=|\mathbb{Z}_{p^e}^*\\
|
|
\Leftrightarrow\hspace{10mm}<g>&=\mathbb{Z}_{p^e}^*
|
|
\end{aligned}$$
|
|
\end{mybox}
|
|
Hierbei gilt:
|
|
\begin{mybox}
|
|
Für ein primitives Element $g\in\mathbb{Z}_p^*$ gilt mit $a:=g^{\frac{o_{p^e}(g)}{p-1}}$:
|
|
$$\begin{aligned}
|
|
\mathbb{Z}_{p^e}^*&=<a>\cdot <1+p>\\
|
|
:&=\{a^i\cdot (1+p)^j\mid i=0,1,...,p-2; j=0,1,...p^{e-1}-1\}
|
|
\end{aligned}$$
|
|
\end{mybox}
|
|
|
|
\subsection{$\mathbb{Z}_{2^e}^*$}
|
|
Die Primzahl 2 stellt eine besonderheit dar, da $\mathbb{Z}_{2^e}^*$ für $e\ge3$ nicht zyklisch ist.
|
|
So gilt $o(5)=2^{e-2}$ und allgemein:
|
|
$$\begin{aligned}
|
|
\mathbb{Z}_{2^e}^*&=<2^e-1>\cdot <5>\\
|
|
&= \{(2^e-1)^i\cdot 5^j\mid i=0,1;j=0,1,...,2^{e-2}-1\}
|
|
\end{aligned}$$
|
|
|
|
\section{Der chinesische Restsatz}
|
|
Für eine Menge teilerfremder Zahlen $\{(n_1,...,n_r)\mid n_i\in\mathbb{N}\}$ bildet einen Menge $\{(a_1,...,a_r)\mid a_i\in\mathbb{Z}\}$ ein System aus Kongruenzen:
|
|
$$\begin{aligned}
|
|
x\equiv&a_1\hspace{10mm} &(\textbf{mod }n_1)\\
|
|
x\equiv&a_2 &(\textbf{mod } n_2)\\
|
|
\vdots\\
|
|
x\equiv&a_r &(\textbf{mod } n_r)\\
|
|
\end{aligned}$$
|
|
Die Menge der ganzzahligen Lösungen ist gegeben durch:
|
|
$$\mathbb{L}=\{a+v\cdot n_1n_2\cdots n_r\mid v\in\mathbb{Z}\}$$
|
|
Hierbei ist $0\le a < n_1n_2\cdots n_r$ eindeutig.
|
|
$a$ wird im folgenden Beispiel mithilfe des erweiterten Euklid'schen Algorithmus (siehe \ref{erweiterter Euklid}) berechnet.
|
|
Aus dem Restsatz leitet sich folgender Satz ab:
|
|
\begin{mybox}
|
|
Sind $n_1,n_2,...,n_r$ paarweise teilerfremde Zahlen gibt es die folgende Isomorphie (\ref{Isomorphie}):
|
|
$$\mathbb{Z}_{n_1n_2\cdots n_r}\cong \mathbb{Z}_{n_1}\times \mathbb{Z}_{n_2}\times\cdots\times\mathbb{Z}_{n_r}$$
|
|
\end{mybox}
|
|
|
|
\subsection{Beispiel}
|
|
folgende Kongruenzen sind gegeben:
|
|
$$\begin{aligned}
|
|
x\equiv&2\hspace{10mm}&(\textbf{mod }5)\\
|
|
x\equiv&7 &(\textbf{mod }2)\\
|
|
x\equiv&2 &(\textbf{mod }5)\\
|
|
\end{aligned}$$
|
|
\begin{itemize}
|
|
\item \textbf{Bestimmung von} $e_1$\\
|
|
für $n_1=5$ und $m_1=21\cdot 11=231$ liefert der erweiterte Euklid'sche Algorithmus (\ref{erweiterter Euklid}):
|
|
$$(-46)\cdot 5+1\cdot 231 = 1$$
|
|
Daher ist $e_1 = 1\cdot 231$
|
|
\item \textbf{Bestimmung von} $e_2$\\
|
|
für $n_2=21$ und $m_2=5\cdot 11=55$ liefert der erweiterte Euklid'sche Algorithmus (\ref{erweiterter Euklid}):
|
|
$$(-21)\cdot 21+(-8)\cdot 55 = 1$$
|
|
Daher ist $e_2 = (-8)\cdot 55=-440$
|
|
\item \textbf{Bestimmung von} $e_3$\\
|
|
für $n_3=11$ und $m_3=5\cdot 21=105$ liefert der erweiterte Euklid'sche Algorithmus (\ref{erweiterter Euklid}):
|
|
$$(-19)\cdot 11+2\cdot 105 = 1$$
|
|
Daher ist $e_3 = 2\cdot 105=210$
|
|
\item \textbf{Berechnung der Lösung}\\
|
|
$n=5\cdot 21\cdot 11=1155$:
|
|
$$\begin{aligned}
|
|
a=&(2\cdot e_1+7\cdot e_2+6\cdot e_3)\mod 1155\\
|
|
=&(2\cdot 231-7\cdot 440+6\cdot 210)\mod 1155\\
|
|
=&-1358\mod 1155\\
|
|
=952
|
|
\end{aligned}$$
|
|
\end{itemize}
|
|
|
|
\section{Elemente gerader und ungerader Ordnung in $\mathbb{Z}_n$**}
|
|
siehe Skript 3 Kapitel 1.4 auf Seite 17(23). |