L'interaction des informations des abonnés dans les réseaux informatiques et de communication est sujette à des perturbations qui entraînent l'apparition d'erreurs et de perturbations de diverses natures. Outre les erreurs dans les messages transmis, un accès non autorisé au contenu des messages du délinquant est possible. La lutte contre ces phénomènes indésirables dure depuis des millénaires, mais avec un succès variable. Les créateurs d'Internet ne l'ont pas du tout conçu tel qu'il est actuellement. Ils ne pensaient même pas aux hackers alors.
Les principaux problèmes théoriques de la confrontation de l'information, les tâches pour les résoudre sont assignés aux théories de la codologie, de la cryptologie et de la stéganologie, dans lesquelles les directions de la codo-analyse, de la cryptanalyse et de la stéganalyse se développent intensivement dans le monde entier. Les aspects pratiques ne restent pas non plus à l'écart, mais je noterai qu'en Fédération de Russie l'activité n'est pas très élevée, l'inertie des jeunes affecte (j'ai moi-même déjà échangé la 9e décennie, mais l'administration Habr a limité la limite d'âge en 1950). Mon opinion, bien sûr, se limite à l'observation de la progéniture (jusqu'aux arrière-petits-enfants) et à la communication sur Internet, ainsi qu'avec les stagiaires et les employés de l'entreprise où je travaille à temps partiel. Les médias ajoutent également de la négativité. Certains jeunes sont devenus un peu plus sages, traversez la colline. Vous pouvez voir vous-même le comportement des autres.
Visite guidée des publications
Le développement (synthèse) de dispositifs techniques requiert du développeur certaines connaissances, la capacité de les utiliser et d'autres compétences de ce type. Les mathématiques sont une composante essentielle de ces connaissances. Il s'agit en règle générale de l'algèbre, des mathématiques discrètes, de la géométrie, de la physique, de la logique mathématique, etc. Ma tâche principale est d'assurer l'accessibilité et la clarté de la présentation des choses que j'utilise dans mes textes et mes recherches.
Par exemple, ici le champ d'extension GF est utilisé (2 8) et, si nous nous en passons, rien de valable ne peut être dit. Mes critères d'évaluation sont simples. Chaque semestre 2, voire 3 examens et tests dans différents groupes d'étude. Là, j'entends et vois ce que j'ai exposé, mis en pratique et ce qui m'est retourné dans les réponses sur les billets d'examen. L'analyse des réponses aux examens est très utile, je vois que quelque chose aurait dû être énoncé différemment, mieux.
Et ici les propriétés Z NLes anneaux de résidus numériques finis modulo le composite N = pq permettent de trouver une solution au problème de la factorisation des grands nombres dans le cadre d'une nouvelle approche originale. Il est clair que dans chacune des publications ultérieures, il serait déraisonnable de transférer une partie des outils mathématiques standard, par conséquent, il a été décidé de tout rassembler en un seul endroit et, si nécessaire, de s'adresser aux lecteurs ici.
Ici, un groupe de points d'une courbe elliptique sur un plan est considéré et utilisé. L'opération de sommation dans un groupe est d'un type très spécial, provoquant des questions déroutantes, comme comment arrivez-vous à ajouter les points de la courbe, même de la part des membres du HEC.
Groupes
Nous introduisons d'abord un certain nombre de définitions nécessaires.
Définition . Ensemble fini A -set, collection de n objets quelconqueslistés dans n'importe quel ordre mais pas de doublons. Les ensembles peuvent être structurés, sur les éléments desquels une (ou plusieurs) opérations et relations sont spécifiées, et non structurés, lorsqu'aucune opération n'est spécifiée.
Ci - dessous, comme un rappel, une table d'actions (opérations) avec des ensembles discrets finis est donné, et pour plus de clarté, les diagrammes montrent également des ensembles continus A et B.
Tableau des opérations avec des ensembles
Définition . Une opération est une application A × A → A ou, par exemple, a · b = c; a, b, c ∊ A. Les opérations dans des structures algébriques autres qu'en arithmétique sont considérées: unaire (par exemple, inversion b -1 ), binaire, ternaire, ..., n-aire (selon le nombre de places pour les opérandes), ou multiplication permutations, modulaires (prenant le résultat par (mod R)), etc. On dit que les éléments a et b permutent ou commutent si ab = ba.
Définition . Un groupe est un ensemble d'éléments G (de toute nature) sur lesquels une seule opération est spécifiée, mais il peut s'agir d'addition (+) et le groupe est appelé additif , son élément neutre (0) ou multiplication (◦) est appelé multiplicatif, son élément neutre (1), mais en règle générale, ces opérations ne sont pas de l'arithmétique ordinaire, mais des opérations spéciales. Le groupe est souvent désigné par le symbole (G, ◦); parmi tous les groupes, une place importante est donnée aux groupes symétriquespermutations de degré n. Les parties des éléments d'un groupe qui conservent les propriétés d'un groupe sont appelées sous-groupes. En substance, ce sont les mêmes groupes, seulement plus petits que l'original. Il s'agit d'une définition informelle d'un groupe, la définition formelle sera donnée un peu plus tard.
Le groupe G, qui satisfait la loi commutative ba = ab pour tout a, b ε G est appelé d'après le mathématicien Abel (1802 -1829) abélien .
Un exemple de groupe additif est l'ensemble des mots du code de Hamming ( voir ici). L'opération dans ce groupe est d'ordre 16 - sommation des mots par (mod2). Avec ce groupe, l'opération de décomposition en classes contiguës d'un groupe de 128 mots par le sous-groupe du code a été réalisée, et la table Keli a également été construite, les éléments du groupe sont utilisés dans l'encodeur (base d'espace de dimension 4) et le décodeur. En un mot, cet exemple montre clairement comment même un petit groupe peut être utilisé pour résoudre un problème pratique très important (communication).
Les groupes de permutation symétrique (permutation) sont très importants dans la théorie des groupes. Cette importance est déterminée par le théorème, qui dit que pour tout groupe apparaissant dans un domaine arbitraire, il existe un groupe symétrique (sous-groupe) qui lui est isomorphe sur les permutations. Ensuite, la tâche de l'étudier est simplifiée pour le chercheur d'un nouveau groupe ouvert. Presque toutes les propriétés du groupe de permutation isomorphe sont également valables dans le nouveau groupe.
Commençons par un exemple simple. N éléments sont donnés (nous les désignons par les nombres 1,2,3, ..., n) et nous en formons des permutations dont le nombre est n! = 1 2 3 ... n. Limitons-nous à la valeur n = 3, puis 3! = 6.
Définition . Ordre des groupes - Le nombre d'éléments dans un groupe est appelé son ordre. Dans l'exemple, le nombre 6 est l'ordre du groupe.
Dans un groupe, chaque élément a également un ordre qui est un diviseur de l'ordre du groupe.
Définition . L'ordre d'un élément d'un groupe est le plus petit exposant d'un élément d'un groupe multiplicatif (multiplicité dans l'additif b + b + b + b + ... b = nb = 0, order = n) auquel il devient un élément neutre, par exemple () 3 = 1, ordre ord () = 3.
Dans le groupe symétriquel'opération est la multiplication des permutations. Cette multiplication est similaire à la multiplication matricielle, puisque chaque permutation de degré n est associée à une matrice de permutation carrée n × n dans laquelle chaque ligne et colonne contient une seule unité. Ceci est illustré ci-dessous pour le groupe symétrique...
Pour faciliter le travail avec un groupe et ses éléments, le mathématicien Keli a proposé un tableau des opérations de groupe (de taille limitée). Dans la cellule à l'intersection d'une ligne et d'une colonne, le résultat de l'opération avec les éléments qui les désignent est mis. Le résultat (ainsi que la désignation des lignes / colonnes) dans le tableau est représenté par des nombres d'éléments décimaux, ce qui économise de l'espace.
Table de multiplication des éléments (permutations) d'un groupe
Le remplissage de 36 cellules de la table de multiplication est simplifié en utilisant les propriétés de la table Keli.
- Toutes les lignes et colonnes contiennent des éléments de l'ensemble du groupe.
- Les colonnes extrêmes sont ordonnées lexicographiquement et dirigées de manière opposée (1er haut / bas - le dernier est vice versa)
- Sur la diagonale principale du tableau il y a des carrés d'éléments, s'il y en a 1, alors l'élément qui lui correspond est l'involution; involutions danssont
- Par rapport aux diagonales de la matrice, la symétrie des positions des éléments est réalisée.
Les propriétés du tableau permettent, lors du remplissage, de restreindre les calculs à seulement 13 paires d'éléments (ils sont indiqués ci-dessus).
Groupe symétrique
Groupe a un petit ordre (6) et n'est pas très pratique pour illustrer les propriétés. Ci-dessous nous donnerons des exemples avec le groupe symétrique24 commandes. Toutes les permutations paires de degré n forment un sous-groupe alterné dans le groupe symétrique, désigné par le symbole A n .
Le tableau 2 peut être utilisé pour trouver les produits de n'importe quelle paire d'élémentsou pour toute leur chaîne, mais sont trouvés par multiplication séquentielle du résultat par l'élément suivant. Vous ne pouvez pas réorganiser les éléments dans l'œuvre. L'opération de multiplication des permutations n'est pas commutative, tout comme la multiplication matricielle. Un élément, lorsqu'il est multiplié par lui-même plusieurs fois jusqu'à ce qu'il se révèle être 1, forme un groupe cyclique de tous les résultats intermédiaires. L'ordre d'un tel sous-groupe cyclique est l'ordre du générateur, il doit diviser l'ordre du grand groupe d'origine.
Selon la table de multiplication, il existe des sous-groupes au sein d'un grand groupe. N'oubliez pas que l'ordre du plus petit sous-groupe doit diviser l'ordre du plus grand.
Nous construisons un groupe cyclique avec l' élément p 14 générant . On entre dans le tableau 2. En ligne 14 on trouve à l'intersection avec p 14élément de colonne p 24 ; à la ligne 24, nous trouvons l'élément p 11 dans la cellule d'intersection avec la colonne 14, et enfin dans la cellule de la ligne 11 à l'intersection avec la colonne 14, nous trouvons l'élément p 1 , c'est-à-dire élément neutre 1. Donc, p 14 · p 14 · p 14 · p 14 = p 1 , ce sont des éléments du sous-groupe d'ordre 4, dont la valeur divise complètement l'ordre 24: 4 = 6. Pour cela, vous pouvez construire la table de Keli et elle ne contient pas n'apparaîtra aucun élément sauf ceux trouvés.Dans ce sous-groupe, les éléments p 14 et p 11 ont le 4ème ordre, et p 24 le second est une involution.
Morphismes de groupe
Une application f d'un groupe (G, *) à un groupe (G ', ◦) est appelée un homomorphisme (ou homomorphisme) si, pour tout a, b ∊ G, f (a * b) = f (a) ◦f (b). Habituellement, ces égalités continuent comme f (e) = e ',
f (a -1 ) = (f (a)) -1 . La notation à droite de l'égalité désigne l'image et s'appelle l'image; à gauche, la pré-image du mappage f. Dans le cas général, les opérations sur l'image et la pré-image ne coïncident pas. L'image inverse de l'identité (G ', ◦) sous l'homomorphisme f est appelée le noyau de cet homomorphisme et est notée ker f. Un exemple bien connu des années scolaires est une telle cartographie
log (a◦b) = log (a) + log (b).
Les éléments de l'image avec une opération sur eux (+), et dans la pré-image les éléments sont reliés par l'opération (◦) de multiplication. Une image homomorphe d'un groupe est un groupe (sous-groupe), c'est-à-dire que si un f-homomorphisme de G sur G 'et G est un groupe, alors G' est aussi un groupe. Un homomorphisme est une généralisation de l'isomorphisme de groupe: si f est une application homomorphique un-à-un de G sur G ', alors il est isomorphe, ce qui est noté G≈G'.
Deux groupes G et G 'avec les opérations (·) et (*) sont dits isomorphes s'il existe un mapping f: G → G' tel que (le mapping f préserve l'opération de groupe) de l'image;
Théorème. Soit H un sous-groupe normal d'un groupe G et G = G / H. Alors l'application f du groupe G sur G donnée par la formule f (a) = aest un homomorphisme. Le noyau de cet homomorphisme est H. Cet homomorphisme est souvent appelé naturel (canonique).
Les homomorphismes de groupe sont essentiellement épuisés par les homomorphismes canoniques.
Décomposons le groupe G d'ordre 24 par rapport à son sous-groupe H = {1,8, 17,24} en cosets et construisons pour cette décomposition un groupe quotient par rapport au sous-groupe H. Pour cela, nous écrivons dans les colonnes les produits gauche et droit des éléments du sous-groupe H.
Dans le tableau de décomposition d'un groupe G d'ordre 24 en cosets par rapport au sous-groupe H, les colonnes l1, l2, l3, l4, l5 sont désignées par les noms de la gauche et n1, n2, n3, n4, n5 - cosets de droite, les principaux représentants des classes, un par colonne, sont écrits en ligne suivante.
La colonne du milieu H est un groupe du quatrième ordre (le noyau de l'homomorphisme). Les colonnes sont remplies avec les produits des principaux représentants des classes et les éléments du groupe H. Une fois les colonnes remplies, les classes sont comparées. Si les compositions des classes gauche et droite coïncident, elles parlent simplement de classes coset et désignent H = K0, K1, K2, K3, K4, K5. De plus, le sous-groupe H est dit normal . Lors du remplissage du tableau, le représentant principal de la classe suivante sélectionne le plus petit élément G parmi ceux qui ne sont pas inclus dans les classes déjà construites.
Les cosets obtenus sont considérés ci-dessous comme des éléments d'un nouveau groupe appelé le groupe quotient du groupe G par le sous-groupe H (le groupe quotient G = G / H est noté ). L'opération dans ce nouveau groupe est la multiplication des classes: pour chaque paire de classes, par exemple, K3 × K5 = K2, une table 4 × 4 est construite, dans laquelle les lignes sont marquées avec les éléments du premier facteur et les colonnes - le second. De plus, la multiplication est effectuée comme dans le groupe G. Le résultat d'une telle multiplication donne 16 éléments, mais ils appartiennent tous à la même classe, dans notre cas la classe K2.
En plus des mappages d'isomorphisme, les homomorphismes sont des endomorphismes et des automorphismes. Un homomorphisme d'un groupe G en lui-même est appelé un endomorphisme, et un isomorphisme d'un groupe G sur lui-même est un automorphisme. Ces concepts sont comparables aux concepts de cartes d'ensembles non structurés par injection, surjection et bijection.
Tableau 2 - Groupe symétrique de Keli$ en ligne $
Commutateur
A chaque couple d'éléments a, b ∊ G on associe un élément appelé le commutateur de ce couple
[a, b] = a -1 b -1 ab. Le sous-groupe K d'un groupe G généré par tous ses commutateurs est appelé le sous-groupe de commutateurs du groupe G ou un sous-groupe dérivé.
Un groupe G est dit résoluble si la chaîne G ⊇ G '⊇ G' '⊇… ⊇ G (i) ⊇ ..., où chaque sous-groupe G (i) est le sous-groupe de commutateurs du précédent, se termine après un nombre fini d'étapes sur le sous-groupe unité, par exemple, G (f) = 1.
Dans le tableau 4, le sous-groupe alterné G '= A 4 d' ordre 12 est normal, à partir de G = d'ordre 24, puisque les cosets gauche et droit de ce sous-groupe coïncident (les classes sont le même complément du groupe complet ). Le tableau 4 est ensuite réduit en un tableau 4 × 4 plus petit (commutateur) contenant les éléments G '' = {1,8,17,24} d'un nouveau sous-groupe dont le commutateur est 1. Le tableau 4 illustre la solvabilité du groupe...
Conclusion
L'article traite de certaines des principales dispositions de la théorie des groupes, qui sont souvent utilisées dans des publications de nature technique (non théorique et mathématique). La compréhension du texte de ces publications est largement déterminée par la possession d'outils mathématiques.
Pour un groupe, un exemple et une technique de sa mise en correspondance homomorphe dans un groupe quotient sont donnés.
Les exemples numériques sont conçus pour servir à assurer l'accessibilité du matériel présenté et dans une large mesure aider à sa compréhension et à son assimilation, avec une analyse minutieuse ou même une répétition avec un crayon à la main. Ce qui manque tout simplement dans les manuels classiques. Ceci est souvent attribué à une économie d'espace et de temps.
J'attends une réaction des lecteurs, qui me dira clairement s'il faut continuer dans ce style ou non.
Littérature
Avdoshin S.M., Nabebin A.A. Mathématiques discrètes. Algèbre modulaire, cryptographie, codage. - M.: DMK Press, 2017.-352 p.
Akimov O.E. Mathématiques discrètes Logique, groupes, graphes - M.: Lab. Base. Zn., 2001.-352 p.
Anderson D.A. Mathématiques discrètes et combinatoire), Moscou: Williams, 2003, 960 p.
Berlekamp E. Théorie du codage algébrique. -M.: Mir, 1971.- 478 p.
Vaulin A.E. Mathématiques discrètes dans les problèmes de sécurité informatique. H 1- SPb.: VKA im. UN F. Mozhaisky, 2015, 219 p.
Vaulin A.E. Mathématiques discrètes dans les problèmes de sécurité informatique. H 2- SPb.: VKA im. UN F. Mozhaisky, 2017.-151 p.
D. Gorenstein, Groupes simples finis. Introduction à leur classification.-M.: Mir, 1985.- 352 p.
Graham R., Knut D., Ptashnik O. Mathématiques concrètes. Fondations de l'informatique.-M.: Mir, 1998.-703 p.
Elizarov V.P. Anneaux d'extrémité. - M.: Helios ARV, 2006. - 304 p.
Ivanov B.N. Mathématiques discrètes: algorithmes et programmes - M.: Lab. Base. Connaissance., 2001.280 p.
Yerusalimsky Y. M. Mathématiques discrètes: théorie, problèmes, applications - M.: Vuzovskaya kniga, 2000. -280 p.
Lidl R., Niederreiter G. Champs finis: en 2 volumes, vol. 1 -M.: Mir, 1988. - 430 p.
Lidl R., Niederreiter G. Champs finis: en 2 volumes, vol. 2 -M.: Mir, 1988. - 392 p.
Lyapin E.S., Aizenshtat A.Ya., Lesokhin M.M., Exercices sur la théorie des groupes - Moscou: Nauka, 1967.-264 p.
Mutter V.M. Fondamentaux de la transmission d'informations anti-brouillage. -L. Energoatomizdat, 1990, 288 p.
A.A. Nabebin, Mathématiques discrètes, Moscou: Laboratoire. Connaissance., 2001.280 p.
F.A. Novikov Mathématiques discrètes pour les programmeurs - SPb.: Peter, 2000.-304 p.
Hall M. Théorie des groupes.-M.: Izd. IL, 1962. - 468 p.
Shikhanovich Yu.A. Groupes, anneaux, treillis. - SPb.: Kirtsideli, 2006. - 368 p.
Shneperman L.B. Un cours d'algèbre et de théorie des nombres en problèmes et exercices: En 2 heures Partie 2.-Mn.: Vysh. shk., 1987.-256 p.
Shneperman L.B. Collection de problèmes d'algèbre et de théorie des nombres - Minsk: Design PRO, 2000. -240 p.