Na matemática, a aritmética modular é um sistema de cálculo para números inteiros, com a ajuda de que eles "viram" quando atingem um determinado valor - o módulo (ou o plural deles). A abordagem moderna para esse tipo de ciência foi desenvolvida por Carl Friedrich Gauss em suas Disquisitiones Arithmeticae publicadas em 1801. Os cientistas da computação gostam muito de usar esse método, pois é muito interessante e abre certas novas possibilidades nas operações com números.
Essência
Como o número de horas recomeça após atingir 12, é módulo aritmético 12. De acordo com a definição abaixo, 12 corresponde não apenas a 12, mas também a 0, então também pode-se nomear o tempo chamado " 12:00 ". "0:00". Afinal, 12 é o mesmo que 0 módulo 12.
A aritmética modular pode ser processada matematicamente introduzindo uma relação congruente para inteiros que seja compatível com operações em inteirosnúmeros: adição, subtração e multiplicação. Para um inteiro positivo n, dois números aeb são ditos congruentes módulo n se sua diferença a - b for um múltiplo de n (isto é, se existir um inteiro k tal que a - b=kn).
Deduções
Na matemática teórica, a aritmética modular é um dos fundamentos da teoria dos números, afetando quase todos os aspectos de seu estudo, e também é amplamente utilizada na teoria de grupos, anéis, nós e álgebra abstrata. No campo da matemática aplicada, é usado em álgebra computacional, criptografia, ciência da computação, química, artes visuais e música.
Prática
Uma aplicação muito prática é o cálculo de checksums em identificadores de números de série. Por exemplo, alguns padrões de livros comuns usam módulo aritmético 11 (se lançado antes de 1º de janeiro de 2007) ou módulo 10 (se lançado antes ou depois de 1º de janeiro de 2007). Da mesma forma, por exemplo, em Números de Conta Bancária Internacional (IBANs). Isso usa a aritmética do módulo 97 para detectar erros de entrada do usuário em números de contas bancárias.
Em química, o último dígito do número de registro CAS (o número de identificação único para cada composto químico) é o dígito verificador. É calculado tomando o último dígito das duas primeiras partes do número de registro CAS multiplicado por 1, o dígito anterior 2 vezes, o dígito anterior 3 vezes, etc., somando tudo e calculando a soma módulo 10.
O que é criptografia? O fato é quetem uma ligação muito forte com o tema em discussão. Na criptografia, as leis da aritmética modular estão diretamente subjacentes aos sistemas de chave pública, como RSA e Diffie-Hellman. Aqui ele fornece os campos finitos subjacentes às curvas elípticas. Usado em vários algoritmos de chave simétrica, incluindo Advanced Encryption Standard (AES), International Data Encryption Algorithm e RC4.
Aplicativo
Este método é usado em áreas onde você precisa ler números. Foi desenvolvido por matemáticos, e todos o usam, especialmente os cientistas da computação. Isso está bem documentado em livros como Modular Arithmetic for Dummies. No entanto, vários especialistas recomendam não levar essa literatura a sério.
Na ciência da computação, a aritmética modular é frequentemente usada em operações bit a bit e outras que envolvem estruturas de dados circulares de largura fixa. Os analistas adoram usá-lo. A operação do módulo é implementada em muitas linguagens de programação e calculadoras. Neste caso, é um exemplo de tal aplicação. Comparação de módulos, divisão com resto e outros truques também são usados na programação.
Na música, o módulo aritmético 12 é usado quando se considera um sistema de temperamento igual de doze tons, no qual a oitava e a enarmônica são equivalentes. Em outras palavras, as teclas na proporção 1-2 ou 2-1 são equivalentes. Na música e outras humanidades, a aritmética desempenha um papel bastante significativo, mas nos livros didáticosos cientistas da computação geralmente não escrevem sobre isso.
Método de redução de noves
O método de conversão 9s oferece uma verificação rápida dos cálculos aritméticos decimais manuais. Baseia-se no módulo aritmético modular 9 e em particular na propriedade decisiva 10 10 1.
há outros exemplos. O módulo aritmético 7 é usado em algoritmos que determinam o dia da semana para uma determinada data. Em particular, a congruência de Zeller e o algoritmo Doomsday fazem uso pesado do módulo aritmético 7.
Outras aplicações
Já foi dito sobre aritmética modular em criptografia. Nesta área, ela é simplesmente insubstituível. De maneira mais geral, a aritmética modular também encontra aplicações em disciplinas como direito, economia (como teoria dos jogos) e outras áreas das ciências sociais. Em outras palavras, onde a divisão e distribuição proporcional dos recursos desempenha um papel importante.
Como a aritmética modular tem uma ampla gama de usos, é importante saber o quão difícil é resolver um sistema de comparações. Um sistema linear de congruências pode ser resolvido em tempo polinomial na forma de eliminação de Gauss. Isso é descrito com mais detalhes pelo teorema da congruência linear. Algoritmos como a redução de Montgomery também existem para permitir que operações aritméticas simples sejam realizadas de forma eficiente. Por exemplo, multiplicação e exponenciação módulo n, para números grandes. Isso é muito importante saber para entender o quecriptografia. Afinal, ele só funciona com operações semelhantes.
Congruência
Algumas operações, como encontrar o logaritmo discreto ou a congruência quadrática, parecem ser tão complexas quanto a fatoração de inteiros e, portanto, são o ponto de partida para algoritmos criptográficos e criptografia. Esses problemas podem ser NP-intermediários.
Exemplos
A seguir estão três funções C bastante rápidas - duas para realizar multiplicação modular e uma para aumentar para números modulares para inteiros sem sinal de até 63 bits, sem estouro transitório.
Pouco depois da descoberta dos inteiros (1, 2, 3, 4, 5…) torna-se evidente que eles são divididos em dois grupos:
- Par: divisível por 2 (0, 2, 4, 6..).
- Ímpar: não divisível por 2 (1, 3, 5, 7…).
Por que essa distinção é importante? Este é o início da abstração. Observamos as propriedades do número (por exemplo, par ou ímpar) e não apenas o próprio número ("37").
Isso nos permite explorar a matemática em um nível mais profundo e encontrar relações entre tipos de números em vez de tipos específicos.
Propriedades de um número
Ser um "três" é apenas mais uma propriedade de um número. Talvez não tão imediatamente útil quanto par/ímpar, mas está lá. Podemos criar regras como "treze x três veias=treze" e assim por diante. Mas é uma loucura. Não podemos criar palavras novas o tempo todo.
A operação do módulo (mod abreviado ou "%" em muitas linguagens de programação) é o restante quandodivisão. Por exemplo, "5 mod 3=2", o que significa que 2 é o resto quando você divide 5 por 3.
Ao converter termos do dia-a-dia para matemática, um "número par" é onde é "0 mod 2", significando que o resto é 0 quando dividido por 2. Um número ímpar é "1 mod 2" (tem um resto de 1).
Números pares e ímpares
O que é par x par x ímpar x ímpar? Bem, é 0 x 0 x 1 x 1=0. Na verdade, você pode ver se um número par é multiplicado em qualquer lugar, onde todo o resultado será zero.
O truque com a matemática modular é que já a usamos para armazenar o tempo - às vezes chamado de "aritmética do relógio".
Por exemplo: 7:00 am (am/pm - não importa). Onde estará o ponteiro das horas daqui a 7 horas?
Modulações
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 é o resto quando 14 é dividido por 12. Equação 14 mod 12=2 mod 12 significa 14 horas e 2 horas mesmo em um relógio de 12 horas. Eles são congruentes, indicados por um triplo sinal de igual: 14 ≡ 2 mod 12.
Outro exemplo: são 8h. Onde estará a grande mão em 25 horas?
Em vez de somar 25 a 8, você pode entender que 25 horas é apenas "1 dia + 1 hora". A resposta é simples. Assim, o relógio terminará 1 hora adiantado - às 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Você converteu intuitivamente 25 para 1 e adicionou isso para 8.
Usando o relógio como analogia, podemos descobrir se oas regras da aritmética modular, e elas funcionam.
Adição/Subtração
Digamos que duas horas pareçam iguais em nosso relógio ("2:00" e "14:00"). Se adicionarmos os mesmos x horas a ambos, o que acontece? Bem, eles mudam pelo mesmo valor no relógio! 2:00 + 5 horas ≡ 14:00 + 5 horas - ambos mostrarão 7:00.
Por quê? Podemos simplesmente adicionar 5 aos 2 restos que ambos têm e eles avançam da mesma maneira. Para todos os números congruentes (2 e 14), a adição e a subtração têm o mesmo resultado.
É mais difícil saber se a multiplicação permanece a mesma. Se 14 ≡ 2 (mod 12), podemos multiplicar os dois números e obter o mesmo resultado? Vamos ver o que acontece quando multiplicamos por 3.
Bem, 2:003 × 6:00. Mas o que é 14:003?
Lembre-se, 14=12 + 2. Então podemos dizer
143=(12 + 2)3=(123) + (23)
A primeira parte (123) pode ser ignorada! O estouro de 12 horas que carrega 14 simplesmente se repete várias vezes. Mas quem se importa? Ignoramos o estouro de qualquer maneira.
Multiplicação
Na multiplicação, apenas o resto importa, ou seja, as mesmas 2 horas para 14:00 e 2:00. Intuitivamente, é assim que vejo a multiplicação não alterando a relação com a matemática modular (você pode multiplicar os dois lados de uma relação modular e obter o mesmo resultado).
Fazemos isso intuitivamente, mas é bom dar um nome. Você tem um voo que chega às 15h. Eleatrasou 14 horas. A que horas vai pousar?
14 ≡ 2 mod 12. Então, pense nisso como 2 horas, então o avião vai pousar às 5 horas da manhã. A solução é simples: 3 + 2=5 da manhã. Isso é um pouco mais complicado do que a operação de módulo simples, mas o princípio é o mesmo.
