Die Informationsinteraktion von Teilnehmern in Computer- und Kommunikationsnetzen unterliegt Störungen, die zu Fehlern und Störungen verschiedener Art führen. Zusätzlich zu Fehlern in den übertragenen Nachrichten ist ein unbefugter Zugriff auf den Inhalt der Nachrichten des Täters möglich. Der Kampf gegen diese unerwünschten Phänomene dauert seit Jahrtausenden an, jedoch mit unterschiedlichem Erfolg. Die Macher des Internets haben es überhaupt nicht so gedacht, wie es jetzt ist. Sie haben damals nicht einmal an Hacker gedacht.
Die wichtigsten theoretischen Probleme der Informationskonfrontation und deren Lösung sind den Theorien der Kodologie, Kryptologie und Steganologie zugeordnet, in denen sich die Richtungen der Kodoanalyse, Kryptoanalyse und Steganalyse weltweit intensiv entwickeln. Praktische Aspekte bleiben ebenfalls nicht unberücksichtigt, aber ich werde feststellen, dass in der Russischen Föderation die Aktivität nicht sehr hoch ist, die Trägheit der jungen Betroffenen (ich selbst habe bereits das 9. Jahrzehnt ausgetauscht, aber die Habr-Regierung hat die Altersgrenze 1950 begrenzt). Meine Meinung beschränkt sich natürlich auf die Beobachtung von Nachkommen (bis zu Urenkelkindern) und die Kommunikation im Internet sowie mit Auszubildenden und Mitarbeitern des Unternehmens, in dem ich Teilzeit arbeite. Die Medien fügen auch Negativität hinzu. Einige der Jugendlichen sind etwas weiser geworden, gehen über den Hügel. Sie können das Verhalten der anderen selbst sehen.
Führung durch Publikationen
Die Entwicklung (Synthese) technischer Geräte erfordert vom Entwickler bestimmte Kenntnisse, die Fähigkeit, sie zu verwenden, und andere Fähigkeiten dieser Art. Ein wesentlicher Bestandteil dieses Wissens ist die Mathematik. Dies sind in der Regel Algebra, diskrete Mathematik, Geometrie, Physik, mathematische Logik usw. Hier im Artikel werden algebraische Strukturen nicht vollständig in der klassischen Darstellung betrachtet, sondern mit einem ausreichenden Maß an Genauigkeit und Genauigkeit. Meine Hauptaufgabe ist es, die Zugänglichkeit und Klarheit der Darstellung von Dingen sicherzustellen, die ich in meinen Texten und Recherchen verwende.
Hier wird beispielsweise das GF-Erweiterungsfeld verwendet (2 8) und wenn wir darauf verzichten, kann nichts Wertvolles festgestellt werden. Meine Bewertungskriterien sind einfach. Jedes Semester 2 oder sogar 3 Prüfungen und Tests in verschiedenen Lerngruppen. Dort höre und sehe ich, was ich dargelegt, in die Praxis umgesetzt und was mir in den Antworten auf den Prüfungskarten zurückgegeben wird. Die Analyse der Prüfungsantworten ist sehr nützlich, ich sehe, dass etwas anders hätte gesagt werden sollen, besser.
Und hier die Eigenschaften Z N.eines endlichen numerischen Restringmoduls werden die zusammengesetzten N = pq verwendet, um eine Lösung für das Problem der Faktorisierung großer Zahlen im Rahmen eines neuen ursprünglichen Ansatzes zu finden. Es ist klar, dass es in jeder der nachfolgenden Veröffentlichungen unangemessen wäre, einen Teil der mathematischen Standardwerkzeuge zu übertragen. Daher wurde beschlossen, alles an einem Ort zu sammeln und gegebenenfalls die Leser hier anzusprechen.
Hier wird eine Gruppe von Punkten einer elliptischen Kurve in einer Ebene betrachtet und verwendet. Die Summierungsoperation in einer Gruppe ist von einer ganz besonderen Art und wirft verwirrende Fragen auf, z. B. wie Sie es schaffen, die Punkte der Kurve selbst von Mitgliedern der HEC hinzuzufügen.
Gruppen
Wir führen zunächst eine Reihe notwendiger Definitionen ein.
Definition . Endliche Menge A- Menge, Sammlung von n Objektenin beliebiger Reihenfolge aufgeführt, jedoch keine Duplikate. Mengen können strukturiert werden, über deren Elemente eine (oder mehrere) Operationen und Beziehungen angegeben werden, und unstrukturiert, wenn keine Operationen angegeben werden.
Zur Erinnerung wird unten eine Tabelle von Aktionen (Operationen) mit endlichen diskreten Mengen angegeben, und der Übersichtlichkeit halber zeigen die Diagramme auch fortlaufende Mengen A und B.
Tabelle von Operationen mit Mengen
Definition . Eine Operation ist eine Abbildung A × A → A oder beispielsweise a · b = c; a, b, c ∊ A. Operationen in anderen algebraischen Strukturen als in der Arithmetik werden berücksichtigt: unär (z. B. Inversion b -1 ), binär, ternär, ..., n-ary (entsprechend der Anzahl der Stellen für Operanden) oder Multiplikation Permutationen, modular (unter Verwendung des Ergebnisses durch (mod R)) usw. Die Elemente a und b sollen permutieren oder pendeln, wenn ab = ba.
Definition . Eine Gruppe ist eine Menge von G-Elementen (beliebiger Art), über die eine einzelne Operation angegeben wird. Sie kann jedoch eine Addition (+) sein, und die Gruppe wird als additiv bezeichnet , ihr neutrales Element (0) oder ihre Multiplikation (◦) wird als multiplikativ bezeichnet, sein neutrales Element (1), aber in der Regel sind diese Operationen keine gewöhnliche Arithmetik, sondern spezielle. Die Gruppe wird oft mit dem Symbol (G, ◦) bezeichnet, wobei symmetrischen Gruppen unter allen Gruppen ein wichtiger Platz eingeräumt wirdPermutationen vom Grad n. Teile der Elemente einer Gruppe, die die Eigenschaften einer Gruppe beibehalten, werden als Untergruppen bezeichnet. Im Wesentlichen handelt es sich um dieselben Gruppen, die nur kleiner als das Original sind. Dies ist eine informelle Definition einer Gruppe, die formelle wird etwas später gegeben.
Die Gruppe G, die das kommutative Gesetz ba = ab für alle a, b ε G erfüllt, wird nach dem Mathematiker Abel (1802-1829) Abelian benannt .
Ein Beispiel für eine additive Gruppe sind die Wörter des Hamming-Codes ( siehe hier)). Die Operation in dieser Gruppe ist 16. Ordnung - Summierung von Wörtern durch (mod2). Mit dieser Gruppe wurde die Operation der Zerlegung in zusammenhängende Klassen einer Gruppe von 128 Wörtern durch eine Untergruppe des Codes durchgeführt, und es wurde auch eine Keli-Tabelle erstellt, wobei die Elemente der Gruppe im Codierer (Basis des Raums der Dimension 4) und im Decodierer verwendet werden. Mit einem Wort, dieses Beispiel zeigt deutlich, wie selbst eine kleine Gruppe verwendet werden kann, um ein sehr wichtiges praktisches Problem (Kommunikation) zu lösen.
Symmetrische Permutationsgruppen (Permutationsgruppen) sind in der Gruppentheorie sehr wichtig. Diese Bedeutung wird durch den Satz bestimmt, der besagt, dass für jede Gruppe, die in einem beliebigen Themenbereich entsteht, eine symmetrische Gruppe (Untergruppe) vorhanden ist, die bei Permutationen isomorph zu dieser ist. Dann wird die Aufgabe des Studiums für den Forscher einer neuen offenen Gruppe vereinfacht. Fast alle Eigenschaften der isomorphen Permutationsgruppe gelten auch für die neue Gruppe.
Beginnen wir mit einem einfachen Beispiel. N Elemente sind gegeben (wir bezeichnen sie mit den Zahlen 1,2,3, ..., n) und wir bilden daraus Permutationen, deren Anzahl n ist! = 1 2 3 ... n. Beschränken wir uns auf den Wert n = 3, dann 3! = 6.
Definition . Gruppenreihenfolge - Die Anzahl der Elemente in einer Gruppe wird als Reihenfolge bezeichnet. Im Beispiel ist die Nummer 6 die Reihenfolge der Gruppe.
In einer Gruppe hat jedes Element auch eine Reihenfolge, die ein Teiler der Gruppenreihenfolge ist.
Definition . Die Reihenfolge eines Elements einer Gruppe ist der kleinste Exponent eines Elements in einer multiplikativen Gruppe (Multiplizität im Additiv b + b + b + b + ... b = nb = 0, Reihenfolge = n), bei dem es beispielsweise zu einem neutralen Element wird () 3 = 1, order ord () = 3.
In der symmetrischen GruppeOperation ist die Multiplikation von Permutationen. Diese Multiplikation ähnelt der Matrixmultiplikation, da jede Permutation des Grades n einer n × n quadratischen Permutationsmatrix zugeordnet ist, in der jede Zeile und Spalte eine einzelne Einheit enthält. Dies ist unten für die symmetrische Gruppe gezeigt...
Um die Arbeit mit einer Gruppe und ihren Elementen zu vereinfachen, schlug der Mathematiker Keli eine Tabelle mit Gruppenoperationen (von begrenzter Größe) vor. In der Zelle am Schnittpunkt einer Zeile und einer Spalte wird das Ergebnis der Operation mit den Elementen, die sie bezeichnen, abgelegt. Das Ergebnis (sowie die Bezeichnung der Zeilen / Spalten) in der Tabelle wird durch dezimale Elementnummern dargestellt, was Platz spart.
Multiplikationstabelle der Elemente (Permutationen) einer Gruppe
Das Ausfüllen von 36 Zellen der Multiplikationstabelle wird durch die Verwendung der Eigenschaften der Keli-Tabelle vereinfacht.
- Alle Zeilen und Spalten enthalten Elemente der gesamten Gruppe.
- Die extremen Spalten sind lexikographisch geordnet und entgegengesetzt gerichtet (1. oben / unten - die letzte ist umgekehrt).
- Auf der Hauptdiagonale der Tabelle befinden sich Quadrate von Elementen. Wenn es 1 gibt, ist das entsprechende Element eine Involution. Involutionen insind
- In Bezug auf die Diagonalen der Matrix wird die Symmetrie der Positionen der Elemente durchgeführt.
Die Eigenschaften der Tabelle ermöglichen es beim Ausfüllen, die Berechnungen auf nur 13 Elementpaare zu beschränken (sie sind oben gezeigt).
Symmetrische Gruppe
Gruppe hat eine kleine Ordnung (6) und ist zur Veranschaulichung von Eigenschaften nicht sehr praktisch. Nachfolgend geben wir Beispiele mit der symmetrischen Gruppe24 Bestellungen. Alle geraden Permutationen des Grades n bilden eine alternierende Untergruppe in der symmetrischen Gruppe, die mit dem Symbol A n bezeichnet ist .
Tabelle 2 kann verwendet werden, um die Produkte eines beliebigen Elementpaares zu findenoder für ihre gesamte Kette, werden aber durch sequentielle Multiplikation des Ergebnisses mit dem nächsten Element gefunden. Sie können die Elemente in der Arbeit nicht neu anordnen. Die Operation des Multiplizierens von Permutationen ist nicht kommutativ, ebenso wie die Matrixmultiplikation. Ein Element bildet, wenn es viele Male mit sich selbst multipliziert wird, bis es sich als 1 herausstellt, eine zyklische Gruppe aller Zwischenergebnisse. Die Reihenfolge einer solchen zyklischen Untergruppe ist die Reihenfolge des Generators, sie muss die Reihenfolge der ursprünglichen großen Gruppe teilen.
Gemäß der Multiplikationstabelle gibt es Untergruppen innerhalb einer großen Gruppe. Es ist zu beachten, dass die Reihenfolge der kleineren Untergruppe die Reihenfolge der größeren teilen muss.
Wir konstruieren eine zyklische Gruppe, wobei das Element p 14 erzeugt wird . Wir geben Tabelle 2 ein. In Zeile 14 finden wir am Schnittpunkt mit p 14Spaltenelement p 24 ; in Zeile 24 finden wir das Element p 11 in der Schnittzelle mit Spalte 14, und schließlich finden wir in der Zelle von Zeile 11 am Schnittpunkt mit Spalte 14 das Element p 1 , d.h. neutrales Element 1. Also, p 14 · p 14 · p 14 · p 14 = p 1 , das sind Elemente der Untergruppe 4. Ordnung, deren Wert die Ordnung 24: 4 = 6 vollständig teilt. Dafür können Sie die Keli-Tabelle erstellen und dies nicht Es erscheinen keine Elemente außer den gefundenen. In dieser Untergruppe haben die Elemente p 14 und p 11 die 4. Ordnung und p 24 die zweite ist eine Involution.
Gruppenmorphismen
Eine Abbildung f einer Gruppe (G, *) auf eine Gruppe (G ', ◦) wird als homomorph (oder Homomorphismus) bezeichnet, wenn für a, b ∊ G f (a * b) = f (a) ◦f (b) ist. Normalerweise setzen sich diese Gleichungen fort als f (e) = e ',
f (a -1 ) = (f (a)) -1 . Die Notation rechts von der Gleichheit bezeichnet das Bild und wird als Bild bezeichnet, links das Vorbild der Abbildung f. Im allgemeinen Fall stimmen die Operationen an Bild und Vorbild nicht überein. Das inverse Bild der Identität (G ', ◦) unter dem Homomorphismus f wird als Kern dieses Homomorphismus bezeichnet und mit ker f bezeichnet. Ein bekanntes Beispiel aus Schuljahren ist ein solches Mapping-
Protokoll (a◦b) = log (a) + log (b).
Elemente des Bildes mit einer Operation darauf (+), und im Vorbild sind die Elemente durch die Operation (◦) der Multiplikation verbunden. Ein homomorphes Bild einer Gruppe ist eine Gruppe (Untergruppe), dh wenn ein f-Homomorphismus von G auf G 'und G eine Gruppe ist, dann ist G' auch eine Gruppe. Ein Homomorphismus ist eine Verallgemeinerung des Gruppenisomorphismus: Wenn f eine homomorphe Eins-zu-Eins-Abbildung von G auf G 'ist, dann ist es isomorph, was als G≈G' bezeichnet wird.
Zwei Gruppen G und G 'mit den Operationen (·) und (*) werden als isomorph bezeichnet, wenn eine Abbildung f: G → G' existiert, so dass (die Abbildung f behält die Gruppenoperation bei) des Bildes;
Satz. Sei H eine normale Untergruppe einer Gruppe G und G = G / H. Dann ist die Abbildung f der Gruppe G auf G gegeben durch die Formel f (a) = aist ein Homomorphismus. Der Kern dieses Homomorphismus ist H. Dieser Homomorphismus wird oft als natürlich (kanonisch) bezeichnet.
Gruppenhomomorphismen werden im Wesentlichen durch kanonische Homomorphismen erschöpft.
Zerlegen wir die Gruppe G der Ordnung 24 in Bezug auf ihre Untergruppe H = {1,8, 17,24} in Cosets und konstruieren für diese Zerlegung eine Quotientengruppe in Bezug auf die Untergruppe H. Zu diesem Zweck schreiben wir in Spalten die linken und rechten Produkte von Elementen der Untergruppe H.
In der Zerlegungstabelle einer Gruppe G der Ordnung 24 in Cosets in Bezug auf die Untergruppe H sind die Spalten l1, l2, l3, l4, l5 mit den Namen der linken und n1, n2, n3, n4, n5 bezeichnet - rechte Cosets, die führenden Vertreter der Klassen, eine pro Spalte, sind in geschrieben nächste Zeile.
Die mittlere Spalte H ist eine Gruppe vierter Ordnung (der Kern des Homomorphismus). Die Spalten werden mit den Produkten der führenden Vertreter der Klassen und den Elementen der Gruppe H gefüllt. Nach dem Ausfüllen der Spalten werden die Klassen verglichen. Wenn die Zusammensetzungen der linken und rechten Klasse übereinstimmen, sprechen sie einfach von Nebenmengenklassen und bezeichnen H = K0, K1, K2, K3, K4, K5. Darüber hinaus wird die Untergruppe H als normal bezeichnet . Beim Ausfüllen der Tabelle wählt der führende Vertreter der nächsten Klasse das kleinste Element G aus denjenigen aus, die nicht in den bereits erstellten Klassen enthalten sind.
Die erhaltenen Nebenmengen werden nachstehend als Elemente einer neuen Gruppe betrachtet, die von der Untergruppe H als Quotientengruppe der Gruppe G bezeichnet wird (die Quotientengruppe G = G / H wird bezeichnet ). Die Operation in dieser neuen Gruppe ist die Multiplikation von Klassen: Für jedes Klassenpaar, zum Beispiel K3 × K5 = K2, wird eine 4 × 4-Tabelle erstellt, in der die Zeilen mit den Elementen des ersten Faktors und die Spalten - die zweite - markiert sind. Ferner wird die Multiplikation wie in Gruppe G durchgeführt. Das Ergebnis einer solchen Multiplikation ergibt 16 Elemente, aber sie gehören alle derselben Klasse an, in unserem Fall der Klasse K2.
Homomorphismen sind neben Isomorphismus-Mappings Endomorphismen und Automorphismen. Ein Homomorphismus einer Gruppe G in sich selbst wird Endomorphismus genannt, und ein Isomorphismus einer Gruppe G in sich selbst ist ein Automorphismus. Diese Konzepte sind vergleichbar mit den Konzepten von Karten unstrukturierter Mengen durch Injektion, Surjektion und Bijektion.
Tabelle 2 - Keli symmetrische Gruppe$ inline $
Kommutator
Jedem Elementpaar a, b ∊ G ordnen wir ein Element zu, das als Kommutator dieses Paares bezeichnet wird
[a, b] = a -1 b -1 ab. Die von allen ihren Kommutatoren erzeugte Untergruppe K einer Gruppe G wird als Kommutator-Untergruppe der Gruppe G oder als abgeleitete Untergruppe bezeichnet.
Eine Gruppe G heißt lösbar, wenn die Kette G ⊇ G '⊇ G' '⊇… ⊇ G (i) ⊇ ..., wobei jede Untergruppe G (i) die Kommutator-Untergruppe der vorherigen ist, nach einer endlichen Anzahl von Schritten auf der Einheits-Untergruppe endet, zum Beispiel G. (f) = 1.
In Tabelle 4 ist die alternierende Untergruppe G '= A 4 der Ordnung 12 von G = normal der Ordnung 24, da die linken und rechten Nebenmengen für diese Untergruppe zusammenfallen (Klassen sind die gleiche Ergänzung zur vollständigen Gruppe ). Tabelle 4 wird dann zu einer kleineren 4 × 4-Tabelle (Kommutator) zusammengefasst, die Elemente G '' = {1,8,17,24} einer neuen Untergruppe enthält, deren Kommutator 1 ist. Tabelle 4 zeigt die Lösbarkeit der Gruppe...
Fazit
Der Artikel beschreibt einige der wichtigsten Bestimmungen der Gruppentheorie, die häufig in Veröffentlichungen technischer (nicht theoretischer und mathematischer) Natur verwendet werden. Das Verständnis des Textes solcher Veröffentlichungen wird weitgehend durch den Besitz mathematischer Werkzeuge bestimmt.
Für eine Gruppe geben wir ein Beispiel und eine Technik für ihre homomorphe Abbildung in eine Quotientengruppe.
Numerische Beispiele sollen dazu dienen, die Verfügbarkeit des präsentierten Materials sicherzustellen und dessen Verständnis und Assimilation durch sorgfältige Analyse oder sogar Wiederholung mit einem Bleistift in der Hand in hohem Maße zu verbessern. Was in den klassischen Handbüchern einfach fehlt. Dies wird häufig auf Platz- und Zeitersparnis zurückgeführt.
Ich warte auf die Reaktion der Leser, die klar machen wird, ob ich in diesem Stil weitermachen soll oder nicht.
Literatur
Avdoshin S.M., Nabebin A.A. Diskrete Mathematik. Modulare Algebra, Kryptographie, Codierung. - M.: DMK Press, 2017.-352 p.
Akimov O.E. Diskrete Mathematik. Logik, Gruppen, Graphen - M .: Lab. Base. Zn., 2001.-352 p.
Anderson D.A. Diskrete Mathematik und Kombinatorik), Moskau: Williams, 2003, 960 p.
Berlekamp E. Algebraische Codierungstheorie. -M.: Mir, 1971.- 478 p.
Vaulin A.E. Diskrete Mathematik bei Computersicherheitsproblemen. H 1- SPb .: VKA im. A.F. Mozhaisky, 2015.219 p.
Vaulin A.E. Diskrete Mathematik bei Computersicherheitsproblemen. H 2 -Spb .: VKA im. A.F. Mozhaisky, 2017.-151 p.
D. Gorenstein, endliche einfache Gruppen. Einführung in ihre Klassifikation.-M .: Mir, 1985.- 352 p.
Graham R., Knut D., Ptashnik O. Konkrete Mathematik. Grundlagen der Informatik.-M .: Mir, 1998.-703 p.
Elizarov V.P. Endringe. - M.: Helios ARV, 2006. - 304 p.
Ivanov B.N. Diskrete Mathematik: Algorithmen und Programme - M .: Lab. Base. Knowledge., 2001.280 p.
Yerusalimsky Y. M. Diskrete Mathematik: Theorie, Probleme, Anwendungen - M .: Vuzovskaya kniga, 2000. -280 p.
Lidl R., Niederreiter G. Endliche Felder: In 2 Bänden. Vol. 1-M .: Mir, 1988. - 430 p.
Lidl R., Niederreiter G. Endliche Felder: In 2 Bänden. Vol. 2-M .: Mir, 1988. - 392 p.
Lyapin E. S., Aizenshtat A. Ya., Lesokhin M. M., Übungen zur Theorie der Gruppen. - Moskau: Nauka, 1967.-264 p.
Mutter V.M. Grundlagen der Anti-Jamming-Informationsübertragung. -L. Energoatomizdat, 1990, 288 p.
A. A. Nabebin, Discrete Mathematics, Moskau: Lab. Knowledge., 2001.280 p.
F. A. Novikov Diskrete Mathematik für Programmierer.- SPb .: Peter, 2000.-304 p.
Hall M. Gruppentheorie.-M .: Izd. IL, 1962.- 468 p.
Shikhanovich Yu.A. Gruppen, Ringe, Gitter. - SPb.: Kirtsideli, 2006. - 368 p.
Shneperman L.B. Ein Kurs in Algebra und Zahlentheorie in Problemen und Übungen: In 2 Stunden Teil 2.-Mn .: Vysh. shk., 1987.-256 p.
Shneperman L.B. Sammlung von Problemen in der Algebra und Zahlentheorie. - Minsk: Design PRO, 2000. -240 p.