Primitive Restklassen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:26 Di 22.09.2009 | | Autor: | D-C |
| Aufgabe | | Aufgabe: Alle primitiven Restklassen modulo 11 bestimmen. |
Hab zuerst mal getestet ob 2 eine Primitivwurzel modulo 11 ist:
[mm] 2^0 \equiv [/mm] 1 (mod 11)
[mm] 2^1 \equiv [/mm] 2
[mm] 2^2 \equiv [/mm] 4
[mm] 2^3 \equiv [/mm] 8
[mm] 2^4 \equiv [/mm] 5
[mm] 2^5 \equiv [/mm] 10
[mm] 2^6 \equiv [/mm] 9
[mm] 2^7 \equiv [/mm] 7
[mm] 2^8 \equiv [/mm] 3
[mm] 2^9 \equiv [/mm] 6
2^10 [mm] \equiv [/mm] 1
Es lassen sich also alle Elemente 1,2,3,...,10 der primen Restklassengruppe
modulo 11 als Potenzen von 2 darstellen.
Soweit dürfte das eigentlich richtig sein denke ich.
Nur wie geht es jetzt weiter? Betrachtet man nun nur noch die Potenzen die Primzahlen und <11 sind bzw. deren Reste ?
Das wären ja dann:
[mm] 2^1 \equiv [/mm] 2 mod 11
[mm] 2^3 \equiv [/mm] 8 mod 11
[mm] 2^5 \equiv [/mm] 10 mod 11
[mm] 2^7 \equiv [/mm] 7 mod11
Also 2,7,8,10 als Lösung.
Nur das Ergebnis soll aber angeblich 2,6,7,8 sein !?
Dazu noch eine Frage unabhängig von der Aufgabe: Kann man nur durch probieren testen ob eine Zahl Primitivwurzel ist, oder gibt es da noch eine elegantere Lösung? Im Bsp. oben mag es ja noch gehen mit modulo 11, aber bei höheren Zahlen, wie z.B. 29 wird das doch recht viel Arbeit denke ich...
Gruß
D-C
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:11 Mi 23.09.2009 | | Autor: | statler |
Hi!
> Aufgabe: Alle primitiven Restklassen modulo 11 bestimmen.
> Hab zuerst mal getestet ob 2 eine Primitivwurzel modulo 11
> ist:
>
> [mm]2^0 \equiv[/mm] 1 (mod 11)
> [mm]2^1 \equiv[/mm] 2
> [mm]2^2 \equiv[/mm] 4
> [mm]2^3 \equiv[/mm] 8
> [mm]2^4 \equiv[/mm] 5
> [mm]2^5 \equiv[/mm] 10
> [mm]2^6 \equiv[/mm] 9
> [mm]2^7 \equiv[/mm] 7
> [mm]2^8 \equiv[/mm] 3
> [mm]2^9 \equiv[/mm] 6
> 2^10 [mm]\equiv[/mm] 1
>
> Es lassen sich also alle Elemente 1,2,3,...,10 der primen
> Restklassengruppe
> modulo 11 als Potenzen von 2 darstellen.
>
> Soweit dürfte das eigentlich richtig sein denke ich.
Ich glaube das auch (ohne Prüfung).
> Nur wie geht es jetzt weiter? Betrachtet man nun nur noch
> die Potenzen die Primzahlen und <11 sind bzw. deren Reste
> ?
>
> Das wären ja dann:
> [mm]2^1 \equiv[/mm] 2 mod 11
> [mm]2^3 \equiv[/mm] 8 mod 11
> [mm]2^5 \equiv[/mm] 10 mod 11
> [mm]2^7 \equiv[/mm] 7 mod11
>
> Also 2,7,8,10 als Lösung.
Nee, so funktioniert das natürlich nicht! Die Ordnung der Gruppe ist 10, also braucht man die zu 10 teilerfremden Exponenten.
In dieser Gruppe ist außerdem 10 = -1, daran siehst du auch sofort die Falschheit deiner Lösung.
> Nur das Ergebnis soll aber angeblich 2,6,7,8 sein !?
Nicht nur angeblich ...
Gruß aus HH-Harburg
Dieter
> Dazu noch eine Frage unabhängig von der Aufgabe: Kann man
> nur durch probieren testen ob eine Zahl Primitivwurzel ist,
> oder gibt es da noch eine elegantere Lösung? Im Bsp. oben
> mag es ja noch gehen mit modulo 11, aber bei höheren
> Zahlen, wie z.B. 29 wird das doch recht viel Arbeit denke
> ich...
PS: Eben deswegen funktionieren ja die darauf basierenden Verschlüsselungsverfahren, der Entschlüsseler wird einfach mürbe gemacht.
>
> Gruß
>
> D-C
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:06 Mi 23.09.2009 | | Autor: | D-C |
> Nee, so funktioniert das natürlich nicht! Die Ordnung der
> Gruppe ist 10, also braucht man die zu 10 teilerfremden
> Exponenten.
> In dieser Gruppe ist außerdem 10 = -1, daran siehst du
> auch sofort die Falschheit deiner Lösung.
Ach das ist der Trick : )
Somit also
[mm] 2^1 [/mm] = 2 mod 11
[mm] 2^3 [/mm] = 8 mod 11
[mm] 2^7 [/mm] = 7 mod 11
[mm] 2^9 [/mm] = 6 mod 11
Dann stimmt auch das Ergebnis.
> Gruß aus HH-Harburg
> Dieter
>
> > Dazu noch eine Frage unabhängig von der Aufgabe: Kann man
> > nur durch probieren testen ob eine Zahl Primitivwurzel ist,
> > oder gibt es da noch eine elegantere Lösung? Im Bsp. oben
> > mag es ja noch gehen mit modulo 11, aber bei höheren
> > Zahlen, wie z.B. 29 wird das doch recht viel Arbeit denke
> > ich...
>
> PS: Eben deswegen funktionieren ja die darauf basierenden
> Verschlüsselungsverfahren, der Entschlüsseler wird
> einfach mürbe gemacht.
Hmm, das macht Sinn. Dann kann man also bei den Aufgaben nur auf nicht allzu hohe Zahlen hoffen : )
Gruß
D-C
|
|
|
|
