Rechen in Z50

14.05.2007, 20:44	Flo rian	Auf diesen Beitrag antworten »
Rechen in Z50 Wie kann ich in $\begin{eqnarray} \mathbb Z_{50} \end{eqnarray}$ $\begin{eqnarray} [3]^{(2^{32})} \end{eqnarray}$ berechnen? Liebe Grüße Flo
14.05.2007, 21:03	AD	Auf diesen Beitrag antworten »
Zunächst mal kann man z.B. den Satz von Fermat-Euler heranziehen, d.h. $\begin{eqnarray} a^{\varphi(m)} \equiv 1 \mod m \end{eqnarray}$ für teilerfremde $\begin{eqnarray} a,m \end{eqnarray}$ . Eine einfache Folgerung daraus ist, dass $\begin{eqnarray} a^x \equiv a^y \mod m \end{eqnarray}$ für $\begin{eqnarray} x\equiv y\mod \varphi(m) \end{eqnarray}$ gilt (die Umkehrung gilt i.a. nicht). Zur Berechnungsvereinfachung $\begin{eqnarray} 3^{2^{32}} \equiv 3^z \mod 50 \end{eqnarray}$ mit einem "kleineren" Exponenten $\begin{eqnarray} z \end{eqnarray}$ kann man ja zunächst ein $\begin{eqnarray} z\equiv 2^{32} \mod \varphi(50) = 2^{32} \mod 20 \end{eqnarray}$ suchen... EDIT: Ok, es geht auch einfacher ohne Einsatz Fermat-Euler: Man betrachte $\begin{eqnarray} x_n = 3^{2^n} \mod 50 \end{eqnarray}$ . Dann ist $\begin{eqnarray} x_{n+1} = 3^{2^{n+1}} = 3^{2^n\cdot 2} = (3^{2^n})^2 = x_n^2 \mod 50 \end{eqnarray}$ Wenn man sich bei diesem "iterierten Quadrieren" so die ersten paar Werte $\begin{eqnarray} x_0, x_1, x_2, \ldots \end{eqnarray}$ anschaut, müsste einem eigentlich was auffallen...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »