[LA1]Übungen

[tavaril]

Hallo zusammen,

da es am Montag zwar bereits eine Übung zu LA, aber noch kein zu besprechendes Übungsblatt gibt, wäre es gut, wenn ihr euch schon mal überlegt, was ihr gerne noch mal wiederholt/erklärt/vertieft bekommen wollt (und das vielleicht sogar hier schon mal ankündigt, dass wir Tutoren uns da mental drauf vorbereiten können ).
Ihr könnt auch gerne Fragen zum Übungsblatt 0 stellen

[duracell]

Hi
Ich fänds sicherlich nicht schlecht wenn noch mal erklärt wird wie das mit den Restklassen ist. Ich kann mir zwar einigermaßen merken wie man die findet, weiss aber nicht wirklich warum man das so macht.

[Robert]

Schön fände ich auch in diesem Zusammenhang nochmal über Einheiten in Restklassen was zu machen und evtl zu Ringen und vielleicht schon mal was zu Körpern. Gehört aber ja irgendwie alles zusammen .

[x2mirko]

Ich habe einige Probleme damit, wie in Aufgabe 3 des Übungsblatts 0 zu bestimmen, ob sich Abbildungen als Verschlüsselungsabbildungen eignen. Wenn das anhand eines etwas komplexeren Bsp. als in der Vorlesung erklärt werden könnte, würde mir das sehr weiterhelfen.

[fw]

Bei der Aufgabe geht es in erster Linie darum, dass eine Verschlüsselungsabbildung eindeutig umkehrbar sein muss (was heisst das?), und nicht z.B. darum wie sicher eine solche Verschlüsselung wäre!

[LonliLokli]

Bei der Aufgabe geht es in erster Linie darum, dass eine Verschlüsselungsabbildung eindeutig umkehrbar sein muss (was heisst das?), und nicht z.B. darum wie sicher eine solche Verschlüsselung wäre!

Das heisst, das es eine Umkehrabbildung gibt.

Um das feststellen zu können, muss man prüfen, ob die Fkt injektiv ist bzw ob es ein multiplikatives Inverses im Restklassenring ex.

[fw]

Das heisst, das ex. eine Umkehrabbildung.

Genau. Ich weiss nicht wieviel ihr in Diskrete zu Ring- und Gruppentheorie gemacht habt, aber es geht im Grunde hier darum sich zu überlegen welche Operationen/Verknüpfungen in einem Ring man "rückgängig machen kann" (kleiner Tipp: eine der beiden Operationen in einem Ring ist immer invertierbar. Die zweite nicht immer (falls sie es doch immer ist, wäre der Ring sogar ein Körper))

[LonliLokli]

Wobei ich habe noch eine Frage:
ist injektiv, ist das auch im Restkalssenring modulo n? Wenn nein, wie findet man am schnellsten ein Gegenbeispiel?(Ausprobieren ist gut, aber git`s vieleicht bessere Methode)

[tromba_marina]

Eine definitive Entscheidungsmöglichkeit fällt mir auf die Schnelle nicht ein, aber man kann sich ein paar Kriterien überlegen:

Zunächst sei n ein Produkt von Primzahlen, in dem mindestens einer der Primfaktoren mehrfach vorkommt, z.B. die Primzahl p. Dann setze a als die Restklasse (n/p) + nZ. Offenbar ist dann a^3 die Nullrestklasse, da (n/p)^3 von n geteilt wird. Also a^3 = 0^3 im Restklassenring, und die Abbildung ist nicht injektiv.

Es bleibt der Fall zu betrachten, dass n quadratfrei ist (kein Primfaktor kommt mehrfach vor).

Sei zunächst n prim, d.h. der Restklassenring ein Körper.
Wenn 3 die Ordnung der Einheitengruppe (also n-1) teilt, dann gibt es Elemente der Ordnung 3, also ist die Abbildung nicht injektiv.
Angenommen, 3 teilt nicht n-1. Dann wähle ein Element a, das die Einheitengruppe erzeugt (d.h. ein Element der Ordnung n-1) -- ihr lernt in LA oder Diskrete Strukturen, dass es das gibt und dass alle zu (n-1) teilerfremden Potenzen davon (insbesondere a^3) ebenfalls die gesamte Einheitengruppe erzeugen. Es gilt Z/nZ = {0, a, a^2, ..., a^(n-1) = 1}. Bildet man die 3-ten Potenzen, erhält man die Menge {0, a^3, (a^3)^2, ..., (a^3)^(n-1)}. Da a^3, wie oben erwähnt, wieder Ordnung n-1 hat, ist das wieder Z/nZ, d.h. die Abbildung ist surjektiv und wegen der Endlichkeit der Menge damit auch injektiv.

Den ersten der beiden Schlüsse kann man verallgemeinern auf die Einheitengruppe eines allgemeinen Restklassenrings Z/nZ (n ab jetzt nicht prim). Es gibt (auch das kommt in LA oder dann in Diskrete Strukturen) phi(n) Einheiten im Restklassenring, die für sich genommen eine Gruppe bilden. Teilt 3 die Zahl phi(n), dann gibt es dort ein Element a der Ordnung 3, und wieder ist a^3 = 1^3 = 1 und die Abbildung nicht injektiv.

Offen bleibt noch: was ist, wenn n ein Produkt paarweise verschiedener Primzahlen ist, und das phi(n)-Kriterium nicht hilft.
Zum Beispiel n = 2*3*5 = 30: phi(30) = 8 hat 3 nicht als Primteiler. Tatsächlich ist die Abbildung in diesem Fall injektiv. Ist das immer so? Wenn jemand Ideen hat, immer her damit.

In jedem Körper der Charakteristik 3 (F3, F9, F27, ...) ist x->x^3 übrigens sogar ein Automorphismus (Frobeniusautomorphismus), also insbesondere injektiv. Von diesen Körpern ist aber nur F3 über Z/3Z als Restklassenring konstruierbar.