Berechnung modularer Potenzen

14.12.2005, 11:07	Andre86	Auf diesen Beitrag antworten »
Berechnung modularer Potenzen Hi Leute! Wie kann ich am besten und kürzesten folgenden Aufgabe lösen? 3^1010101010101010 mod 56
14.12.2005, 11:46	4c1d	Auf diesen Beitrag antworten »
Stelle z.B. die Periodenlänge von $\begin{eqnarray} 3^n \mod 56 \end{eqnarray}$ fest, d.h. suche die erste Zahl n, für die $\begin{eqnarray} 3^n \equiv 1 \mod 56 \end{eqnarray}$ gilt (in diesem Fall recht einfach zu finden). Dann musst du nurnoch herausfinden, zu welcher Zahl $\begin{eqnarray} 1010101010101010 = \sum_{i=1}^8 ~ 10^{2i-1} \end{eqnarray}$ kongruent modulo $\begin{eqnarray} n \end{eqnarray}$ ist. Keine Ahnung ob es einen schnelleren Weg gibt, sich das herzuleiten...
16.12.2005, 00:18	Andre86	Auf diesen Beitrag antworten »
Das ist eine super Lösung! Danke Ist dieser Lösungsweg allgemeingültig? Oder kann ich ihn nur auf diese Aufgabe anwenden?
16.12.2005, 07:15	AD	Auf diesen Beitrag antworten »
Das klappt immer dann, wenn Basis $\begin{eqnarray} b \end{eqnarray}$ und Modul $\begin{eqnarray} m \end{eqnarray}$ teilerfremd sind, wie hier $\begin{eqnarray} b=3 \end{eqnarray}$ und $\begin{eqnarray} m=56 \end{eqnarray}$ . Überdies weiß man sofort, dass das kleinste derartige $\begin{eqnarray} n \end{eqnarray}$ ein Teiler von $\begin{eqnarray} \varphi(m) \end{eqnarray}$ ist, hier also muss wegen $\begin{eqnarray} \varphi(56)=24 \end{eqnarray}$ das $\begin{eqnarray} n \end{eqnarray}$ ein Teiler von 24 sein. Sind $\begin{eqnarray} b \end{eqnarray}$ und $\begin{eqnarray} m \end{eqnarray}$ nicht teilerfremd, muss man das Verfahren modifizieren, z.B. durch Modulaufteilung und dann chinesischer Restsatz.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »