Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » effiziente Berechnung der Ordnung?

effiziente Berechnung der Ordnung?

Universität / Fachhochschule

Algebraische Zahlentheorie

Kryptologie

Primzahlen

Tags: Algebraische Zahlentheorie, Kryptologie, Primzahl

student11 aktiv_icon

09:58 Uhr, 17.02.2012

Wie kann ich in einer Gruppe effizient die Ordnung eines Elements bestimmen?
Konkret möchte ich eigentlich folgende Aufgabe lösen:

R_{120} (7^{23})

berechnen.. Dazu möchte ich

x

finden, sodass

7^{x} (\equiv 120) 1,

doch das ist doch gerade eben die Ordnung von 7 bezüglich

Z ⋆_{120},

oder nicht?
Wie ich das bisher gemacht habe:

< 7 > = {1,7,49,343,2401, ...}

und jeweils den Rest betrachtet, bis ich das richtige Resultat habe.

An der Prüfung dürfen wir keinen Taschenrechner verwenden, Kopfrechnen ist bei Multiplikation von mehrstelligen Zahlen nicht mehr gerade meine Stärke..

Gibt es eine effizientere Methode?

Beispielsweise weiss ich ja, dass die Ordnung von 7 die Gruppenordnung

φ (120)

teilen muss. Ich muss also nur die Teiler von

φ (120) = 2^{2} \cdot 1^{3} \cdot 5^{0} \cdot 4^{1} \cdot 3^{0} \cdot 2^{1} = 32

[

120 = 2^{3} \cdot 5 \cdot 3]

betrachten..

Es kommen also folgende Kandidaten für

x

in Frage:

x \in {1,2,4,8,16,32}

Also überprüfe ich

7^{1} = 7, 7^{2} = 49, 7^{4} = 2401

und sehe, dass

2401 (\equiv 120) 1

ist.
Ich erspare mir also hier das Berechnen von

7^{3} .

.

Doch gibt es eine effizientere Methode?

Für das multiplikative Inverse gibt es ja den Erweiterten Euklidischen Algorithmus, der die Berchnung vor allem bei höheren Zahlen extremst vereinfacht.. Gibt es so was Ähnliches auch für die Ordnung? Wenn nein, könnt ihr mir die erste (Untermenge aufschreiben, überprüfen) oder die zweite Methode (Gruppenordnung berechnen, Teiler als Potenzen überprüfen) empfehlen?

Vielen Dank für eure Hilfe..

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Teilbarkeit natürlicher Zahlen

student11 aktiv_icon

13:35 Uhr, 17.02.2012

Oder wie wäre es, wenn man zuerst überprüft, ob die Gruppe zyklisch ist, und wenn ja, dann über den Isomorphismus geht?

Beispielsweise ist die Ordnung von

9 \in Z ⋆_{14}

gesucht.

14

ist

2 \cdot 7

und daher ist

Z ⋆_{14}

zyklisch..

φ (14) = 6,

daher ist

Z ⋆_{14}

isomorph zu

Z_{6}

.

Daher lässt sich

ψ : Z_{6} \to Z ⋆_{14}

finden

ψ (0) = 1

ψ (1) = 5

ψ (2) = 11

ψ (3) = 13

ψ (4) = 9

ψ (5) = 3

Man sieht hier, dass 9 dem Element 4 enstpricht. 4 hat bezüglich

Z_{6}

das Inverse

2,

somit sollte das Inverse von

911

sein.

9 \cdot 11 = 99 (\equiv 14) 1

Das ist das Multiplikative Inverse..

Nun die Ordnung von 9: Man berechnet schneller die Ordnung von

4 \in Z_{6},

dazu berechnet man den ggT: ggT(4,6)=12
Da

3 \cdot 4 = 12

ist die Ordnung von

43

. Deshalb ist die Ordnung von

9 \in Z ⋆_{14}

auch 3.

Welche Methode macht nun Sinn?

hagman aktiv_icon

15:16 Uhr, 17.02.2012

Es gibt noch ein paar Möglichkeiten, aber nicht allgemeiner Art.
Wenn beispielsweise

a

offensichtlich ein Quadrat ist, dann mus die Ordnung ja sogar ein eher kleiner Teiler vno

φ (n)

sein (da ja das Doppelte auch ein Teiler sein muss).
Ginge es also um 9 statt

7,

hätte das heklfen könenn. Sogar bei

24

statt

7,

da ja

24 \equiv 144 = 12^{2}

.
Aber bei

n = 120,

wenn also

φ (n)

eine Zweirpotenz ist, dürfte wiederholtes Quadrieren das Sinnvollste sein (und zwar auch bei 9 und

24)

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

974030

973986

	Status: nicht eingeloggt	Noch nicht registriert?