A interação de informações de assinantes em redes de computadores e comunicações está sujeita a distúrbios que levam à ocorrência de erros e distúrbios de vários tipos. Além de erros nas mensagens transmitidas, é possível o acesso não autorizado ao conteúdo das mensagens do infrator. A luta contra esses fenômenos indesejáveis vem acontecendo há milênios, mas com sucesso variável. Os criadores da Internet não a conceberam da maneira que é agora. Eles nem pensaram em hackers naquela época.
Os principais problemas teóricos de confronto de informações, as tarefas de resolvê-los são atribuídos às teorias da codologia, criptologia e esteganologia, nas quais as direções da codoanálise, criptanálise e esteganálise estão se desenvolvendo intensamente em todo o mundo. Aspectos práticos também não ficam de lado, mas notarei que na Federação Russa a atividade não é muito alta, a inércia dos jovens afeta (eu mesmo já troquei a 9ª década, mas o governo Habr limitou o limite de idade em 1950). Minha opinião, claro, se limita a observar os filhos (até bisnetos) e a comunicação pela internet, bem como com estagiários e funcionários da empresa onde trabalho. A mídia também está adicionando negatividade. Alguns dos jovens ficaram um pouco mais sábios, subam a colina. Você mesmo pode ver o comportamento dos outros.
Visita guiada às publicações
O desenvolvimento (síntese) de dispositivos técnicos requer do desenvolvedor certos conhecimentos, a habilidade de usá-los e outras habilidades deste tipo. Um componente essencial desse conhecimento é a matemática. Estas são, via de regra, álgebra, matemática discreta, geometria, física, lógica matemática, etc. Aqui no artigo, consideraremos estruturas algébricas não exatamente na apresentação clássica, mas com um nível suficiente de rigor e precisão. Minha principal tarefa é garantir a acessibilidade e clareza na apresentação das coisas que utilizo em meus textos e pesquisas.
Por exemplo, aqui o campo de extensão GF é usado (2 8) e, se fizermos sem ele, nada pode ser declarado. Meus critérios de avaliação são simples. Cada semestre 2, ou mesmo 3 exames e testes em diferentes grupos de estudo. Lá ouço e vejo o que expus, coloquei em prática e o que me é devolvido nas respostas dos bilhetes de exame. A análise das respostas dos exames é muito útil, vejo que algo deveria ter sido dito de forma diferente, melhor.
E aqui as propriedades Z Nde um módulo de anel de resíduo numérico finito, os compostos N = pq são usados para encontrar uma solução para o problema de fatorar grandes números dentro da estrutura de uma nova abordagem original. É claro que em cada uma das publicações subseqüentes não seria razoável transferir parte das ferramentas matemáticas padrão, portanto, decidiu-se reunir tudo em um só lugar e, se necessário, abordar aqui os leitores.
Aqui, um grupo de pontos de uma curva elíptica em um plano é considerado e usado. A operação de soma em um grupo é de um tipo muito especial, causando questões desconcertantes, como como você consegue somar os pontos da curva, mesmo de membros do HEC.
Grupos
Primeiro, apresentamos uma série de definições necessárias.
Definição . Conjunto finito A - coleção de quaisquer n objetoslistado em qualquer ordem, mas sem duplicatas. Os conjuntos podem ser estruturados, sobre cujos elementos uma (ou mais) operação e relações são especificadas, e não estruturados, quando nenhuma operação é especificada.
Abaixo, como um lembrete, uma tabela de ações (operações) com conjuntos discretos finitos é fornecida e, para maior clareza, os diagramas também mostram conjuntos contínuos A e B.
Tabela de operações com conjuntos
Definição . Uma operação é um mapeamento A × A → A ou, por exemplo, a · b = c; a, b, c ∊ A. As operações em estruturas algébricas diferentes da aritmética são consideradas: unário (por exemplo, inversão b -1 ), binário, ternário, ..., n-ário (de acordo com o número de casas para operandos) ou multiplicação permutações, modulares (tomando o resultado por (mod R)), etc. Diz-se que os elementos a e b permutam ou comutam se ab = ba.
Definição . Um grupo é um conjunto de elementos G (de qualquer natureza) sobre os quais uma única operação é especificada, mas pode ser adição (+) e o grupo é chamado de aditivo , seu elemento neutro (0) ou multiplicação (◦) é chamado de multiplicativo, seu elemento neutro (1), mas como regra, essas operações não são aritméticas ordinárias, mas especiais. O grupo é frequentemente denotado pelo símbolo (G, ◦); entre todos os grupos, um lugar importante é dado aos grupos simétricospermutações de grau n. Partes dos elementos de um grupo que preservam as propriedades de um grupo são chamadas de subgrupos. Em essência, esses são os mesmos grupos, apenas menores que o original. Esta é uma definição informal de grupo, a formal será dada um pouco mais tarde.
O grupo G, que satisfaz a lei comutativa ba = ab para todo a, b ε G é chamado em homenagem ao matemático Abel (1802 -1829) Abelian .
Um exemplo de grupo aditivo é o conjunto de palavras do código de Hamming ( veja aqui) A operação neste grupo é de 16ª ordem - soma de palavras por (mod2). Com este grupo, foi realizada a operação de decomposição em classes contíguas de um grupo de 128 palavras pelo subgrupo do código, e também foi construída a tabela de Keli, os elementos do grupo são utilizados no codificador (base do espaço de dimensão 4) e no decodificador. Em suma, este exemplo demonstra claramente como até mesmo um pequeno grupo pode ser usado para resolver um problema prático muito importante (comunicação).
Os grupos de permutação simétrica (permutação) são muito importantes na teoria dos grupos. Esta importância é determinada pelo teorema, que diz que para qualquer grupo surgindo em uma área de assunto arbitrária, há um grupo simétrico (subgrupo) isomorfo a ele nas permutações. Então, a tarefa de estudá-lo é simplificada para o pesquisador de um novo grupo aberto. Quase todas as propriedades do grupo de permutação isomórfica são válidas no novo grupo.
Vamos começar com um exemplo simples. N elementos são dados (nós os denotamos pelos números 1,2,3, ..., n) e formamos permutações deles, o número das quais é n! = 1 2 3 ... n. Vamos nos restringir ao valor n = 3, então 3! = 6.
Definição . Ordem do grupo - O número de elementos em um grupo é chamado de ordem. No exemplo, o número 6 é a ordem do grupo.
Em um grupo, cada elemento também possui uma ordem que é um divisor da ordem do grupo.
Definição . A ordem de um elemento de um grupo é o menor expoente de um elemento em um grupo multiplicativo (multiplicidade no aditivo b + b + b + b + ... b = nb = 0, ordem = n) em que se torna um elemento neutro, por exemplo () 3 = 1, ordem ord () = 3.
No grupo simétricooperação é multiplicação de permutações. Essa multiplicação é semelhante à multiplicação de matriz, uma vez que cada permutação de grau n está associada a uma permutação quadrada n × n matriz em que cada linha e coluna contém uma única unidade. Isso é mostrado abaixo para o grupo simétrico...
Para a conveniência de trabalhar com um grupo e seus elementos, o matemático Kely propôs uma tabela de operações de grupo (de tamanho limitado). Na célula na intersecção de uma linha e uma coluna, é colocado o resultado da operação com os elementos que os denotam. O resultado (bem como a designação de linhas / colunas) na tabela é representado por números de elementos decimais, o que economiza espaço.
Tabela de multiplicação de elementos (permutações) de um grupo
O preenchimento de 36 células da tabela de multiplicação é simplificado usando as propriedades da tabela de Keli.
- Todas as linhas e colunas contêm elementos de todo o grupo.
- As colunas extremas são ordenadas lexicograficamente e dirigidas de forma oposta (1ª parte superior / inferior - a última é vice-versa)
- Na diagonal principal da mesa existem quadrados de elementos, se houver 1, então o elemento correspondente a ela é a involução; involuções emestamos
- Com relação às diagonais da matriz, é realizada a simetria das posições dos elementos.
As propriedades da tabela permitem, ao preenchê-la, restringir os cálculos a apenas 13 pares de elementos (são mostrados acima).
Grupo simétrico
Grupo tem uma ordem pequena (6) e não é muito conveniente para ilustrar propriedades. Abaixo, daremos exemplos com o grupo simétrico24 pedidos. Todas as permutações pares de grau n formam um subgrupo alternado no grupo simétrico, denotado pelo símbolo A n .
A Tabela 2 pode ser usada para encontrar os produtos de qualquer par de elementosou para toda a sua cadeia, mas são encontrados pela multiplicação sequencial do resultado pelo próximo elemento. Você não pode reorganizar os elementos na obra. A operação de multiplicação de permutações não é comutativa, como a multiplicação de matrizes. Um elemento, quando multiplicado por ele mesmo muitas vezes até obter 1, forma um grupo cíclico de todos os resultados intermediários. A ordem de tal subgrupo cíclico é a ordem do gerador; ele deve dividir a ordem do grande grupo original.
De acordo com a tabuada de multiplicação, existem subgrupos dentro de um grande grupo. Lembre-se de que a ordem do subgrupo menor deve dividir a ordem do maior.
Construímos um grupo cíclico com o elemento p 14 gerando . Entramos na tabela 2. Na linha 14, encontramos na interseção com p 14elemento de coluna p 24 ; na linha 24 encontramos o elemento p 11 na célula de interseção com a coluna 14 e, finalmente, na célula da linha 11 na interseção com a coluna 14, encontramos o elemento p 1 , ou seja, elemento neutro 1. Então, p 14 · p 14 · p 14 · p 14 = p 1 , são elementos do subgrupo de 4ª ordem, cujo valor divide completamente a ordem 24: 4 = 6. Para isso, pode-se construir a tabela de Keli e ela não contém não aparecerá nenhum elemento, exceto aqueles encontrados.Neste subgrupo, os elementos p 14 ep 11 têm a 4ª ordem, ep 24 o segundo é uma involução.
Morfismos de grupo
Um mapeamento f de um grupo (G, *) para um grupo (G ', ◦) é chamado de homomórfico (ou homomorfismo) se, para qualquer a, b ∊ G, f (a * b) = f (a) ◦f (b). Normalmente, essas igualdades continuam como f (e) = e ',
f (a -1 ) = (f (a)) -1 . A notação à direita da igualdade denota a imagem e é chamada de imagem; à esquerda, a pré-imagem do mapeamento f. No caso geral, as operações na imagem e na pré-imagem não coincidem. A imagem inversa da identidade (G ', ◦) sob o homomorfismo f é chamada de núcleo desse homomorfismo e é denotada por ker f. Um exemplo bem conhecido de anos escolares é um
log de mapeamento (a◦b) = log (a) + log (b).
Elementos da imagem com uma operação (+), e na pré-imagem os elementos são conectados pela operação (◦) de multiplicação. Uma imagem homomórfica de um grupo é um grupo (subgrupo), ou seja, se um f-homomorfismo de G em G 'e G é um grupo, então G' também é um grupo. Um homomorfismo é uma generalização do isomorfismo de grupo: se f é um mapeamento homomórfico um-para-um de G em G ', então é isomórfico, que é denotado como G≈G'.
Dois grupos G e G 'com operações (·) e (*) são chamados de isomórficos se existir um mapeamento f: G → G' tal que (o mapeamento f preserva a operação do grupo) da imagem;
Teorema. Seja H um subgrupo normal de um grupo G e G = G / H. Então o mapeamento f do grupo G em G dado pela fórmula f (a) = aé um homomorfismo. O cerne desse homomorfismo é H. Esse homomorfismo é freqüentemente chamado de natural (canônico).
Os homomorfismos de grupo são essencialmente exauridos pelos homomorfismos canônicos.
Vamos decompor o grupo G de ordem 24 com respeito ao seu subgrupo H = {1,8, 17,24} em cosets e construir para esta decomposição um grupo quociente com respeito ao subgrupo H. Para este propósito, escrevemos nas colunas os produtos esquerdo e direito dos elementos do subgrupo H.
Na tabela de decomposição de um grupo G de ordem 24 em cosets com respeito ao subgrupo H, as colunas l1, l2, l3, l4, l5 são designadas com os nomes da esquerda e n1, n2, n3, n4, n5 - cosets da direita, os principais representantes das classes, um por coluna, são escritos em próxima linha.
A coluna do meio H é um grupo de quarta ordem (o núcleo do homomorfismo). As colunas são preenchidas com os produtos dos principais representantes das classes e os elementos do grupo H. Após o preenchimento das colunas, as classes são comparadas. Se as composições das classes esquerda e direita coincidem, então elas simplesmente falam de classes de cosets e denotam H = K0, K1, K2, K3, K4, K5. Além disso, o subgrupo H é denominado normal . Ao preencher a tabela, o representante líder da próxima classe seleciona o menor elemento G daqueles não incluídos nas classes já construídas.
Os cosets obtidos são considerados a seguir como elementos de um novo grupo denominado grupo quociente do grupo G pelo subgrupo H (o grupo quociente G = G / H é denotado ). A operação neste novo grupo é a multiplicação de classes: para cada par de classes, por exemplo, K3 × K5 = K2, uma tabela 4 × 4 é construída, na qual as linhas são marcadas com os elementos do primeiro fator, e as colunas - o segundo. Além disso, a multiplicação é realizada como no grupo G. O resultado dessa multiplicação dá 16 elementos, mas todos eles pertencem à mesma classe, em nosso caso a classe K2.
Além dos mapeamentos de isomorfismo, os homomorfismos são endomorfismos e automorfismos. Um homomorfismo de um grupo G sobre si mesmo é chamado de endomorfismo, e um isomorfismo de um grupo G sobre si mesmo é chamado de automorfismo. Esses conceitos são comparáveis aos conceitos de mapas de conjuntos não estruturados por injeção, sobreposição e bijeção.
Tabela 2 - Grupo simétrico Keli$ inline $
Comutador
A cada par de elementos a, b ∊ G associamos um elemento denominado comutador deste par
[a, b] = a -1 b -1 ab. O subgrupo K de um grupo G gerado por todos os seus comutadores é chamado de subgrupo de comutador do grupo G ou um subgrupo derivado.
Um grupo G é chamado de solucionável se a cadeia G ⊇ G '⊇ G' '⊇ ... ⊇ G (i) ⊇ ..., onde cada subgrupo G (i) é o subgrupo comutador do anterior, termina após um número finito de etapas no subgrupo de unidades, por exemplo, G (f) = 1.
Na Tabela 4, o subgrupo alternado G '= A 4 de ordem 12 é normal, de G = da ordem 24, uma vez que os cosets esquerdo e direito para este subgrupo coincidem (as classes são o mesmo complemento do grupo completo ) A Tabela 4 é então recolhida em uma mesa menor 4 × 4 (comutador) contendo os elementos G '' = {1,8,17,24} de um novo subgrupo cujo comutador é 1. A Tabela 4 ilustra a solvabilidade do grupo...
Conclusão
O artigo discute algumas das principais disposições da teoria dos grupos, que são frequentemente utilizadas em publicações de natureza técnica (não teórica e matemática). A compreensão do texto dessas publicações é amplamente determinada pela posse de ferramentas matemáticas.
Para um grupo, são dados um exemplo e uma técnica de seu mapeamento homomórfico em um grupo quociente.
Os exemplos numéricos pretendem servir para garantir a disponibilidade do material apresentado e, em grande medida, ajudar na sua compreensão e assimilação, com análise cuidadosa ou mesmo repetição com um lápis na mão. O que simplesmente está faltando nos manuais clássicos. Isso geralmente é atribuído à economia de espaço e tempo.
Aguardo uma reação dos leitores, que deixará claro se é para continuar neste estilo ou não.
Literatura
Avdoshin S.M., Nabebin A.A. Matemática discreta. Álgebra modular, criptografia, codificação. - M.: DMK Press, 2017.-352 p.
Akimov O.E. Matemática discreta .Lógica, grupos, gráficos - M.: Laboratório. Base. Zn., 2001.-352 p.
Anderson D.A. Discrete mathematics and combinatorics), Moscou: Williams, 2003, 960 p.
Berlekamp E. Teoria da codificação algébrica. -M.: Mir, 1971.- 478 p.
Vaulin A.E. Matemática discreta em problemas de segurança de computadores. H 1- SPb.: VKA im. A.F. Mozhaisky, 2015.219 p.
Vaulin A.E. Matemática discreta em problemas de segurança de computadores. H 2- SPb.: VKA im. A.F. Mozhaisky, 2017.-151 p.
D. Gorenstein, Finite Simple Groups. Introdução à sua classificação. -M.: Mir, 1985.- 352 p.
Graham R., Knut D., Ptashnik O. Concrete Mathematics. Foundations of Informatics.-M.: Mir, 1998.-703 p.
Elizarov V.P. Terminar anéis. - M.: Helios ARV, 2006. - 304 p.
Ivanov B.N. Matemática discreta: algoritmos e programas - M.: Laboratório. Base. Knowledge., 2001.280 p.
Yerusalimsky Y. M. Matemática discreta: teoria, problemas, aplicações - M: Vuzovskaya kniga, 2000.280 p.
Lidl R., Niederreiter G. Finite fields: In 2 volumes.Vol. 1 -M.: Mir, 1988. - 430 p.
Lidl R., Niederreiter G. Finite fields: In 2 volumes.Vol. 2-M.: Mir, 1988. - 392 p.
Lyapin E.S., Aizenshtat A.Ya., Lesokhin M.M., Exercises on the theory of groups.- Moscow: Nauka, 1967.-264 p.
Mutter V.M. Fundamentos da transmissão de informações anti-bloqueio. -EU. Energoatomizdat, 1990, 288 p.
A.A. Nabebin, Discrete Mathematics, Moscou: Lab. Knowledge., 2001.280 p.
F.A. Novikov Discrete mathematics for programmers.- SPb.: Peter, 2000.-304 p.
Hall M. Teoria de Grupo.-M .: Izd. IL, 1962.- 468 p.
Shikhanovich Yu.A. Grupos, anéis, treliças. - SPb.: Kirtsideli, 2006. - 368 p.
Shneperman L.B. O curso de álgebra e teoria dos números em problemas e exercícios: Em 2 horas Parte 2.-Mn.: Vysh. shk., 1987.-256 p.
Shneperman L.B. Coleção de problemas em álgebra e teoria dos números - Minsk: Design PRO, 2000. -240 p.