Aritmética modular - Modular arithmetic
Em matemática , a aritmética modular é um sistema de aritmética para números inteiros , onde os números "se enrolam" ao atingir um determinado valor, denominado módulo . A abordagem moderna da aritmética modular foi desenvolvida por Carl Friedrich Gauss em seu livro Disquisitiones Arithmeticae , publicado em 1801.
Um uso familiar da aritmética modular é no relógio de 12 horas , no qual o dia é dividido em dois períodos de 12 horas. Se a hora for 7:00 agora, então 8 horas depois serão 3:00. A adição simples resultaria em 7 + 8 = 15 , mas os relógios "se ajustam" a cada 12 horas. Como o número da hora recomeça depois de atingir 12, este é o módulo aritmético 12. Em termos da definição abaixo, 15 é congruente com 3 módulo 12, então "15:00" em um relógio de 24 horas é exibido "3:00 "em um relógio de 12 horas.
Congruência
Dado um número inteiro n > 1 , chamado um módulo , dois inteiros um e b são referidos como sendo congruente módulo n , se n é um divisor da sua diferença (isto é, se não houver um número inteiro k de tal modo que uma - b = kn ).
O módulo de congruência n é uma relação de congruência , o que significa que é uma relação de equivalência compatível com as operações de adição , subtração e multiplicação . O módulo de congruência n é denotado:
Os parênteses significam que (mod n ) se aplica a toda a equação, não apenas ao lado direito (aqui b ). Esta notação não deve ser confundida com a notação b mod n (sem parênteses), que se refere à operação do módulo . De fato, b mod n denota o inteiro único a tal que 0 ≤ a < n e (ou seja, o resto de quando dividido por ).
A relação de congruência pode ser reescrita como
mostrando explicitamente sua relação com a divisão euclidiana . No entanto, o b aqui não precisa ser o resto da divisão de a por n . Em vez disso, o que a declaração a ≡ b (mod n ) afirma é que a e b têm o mesmo resto quando divididos por n . Isso é,
onde 0 ≤ r < n é o resto comum. Subtraindo essas duas expressões, recuperamos a relação anterior:
definindo k = p - q .
Exemplos
No módulo 12, pode-se afirmar que:
porque 38 - 14 = 24 , que é um múltiplo de 12. Outra maneira de expressar isso é dizer que 38 e 14 têm o mesmo resto 2, quando dividido por 12.
A definição de congruência também se aplica a valores negativos. Por exemplo:
Propriedades
A relação de congruência satisfaz todas as condições de uma relação de equivalência :
- Reflexividade: a ≡ a (mod n )
- Simetria: a ≡ b (mod n ) se b ≡ a (mod n ) para todo a , b e n .
- Transitividade: Se a ≡ b (mod n ) e b ≡ c (mod n ) , então a ≡ c (mod n )
Se a 1 ≡ b 1 (mod n ) e a 2 ≡ b 2 (mod n ), ou se a ≡ b (mod n ), então:
- a + k ≡ b + k (mod n ) para qualquer inteiro k (compatibilidade com tradução)
- ka ≡ kb (mod n ) para qualquer inteiro k (compatibilidade com escala)
- a 1 + a 2 ≡ b 1 + b 2 (mod n ) (compatibilidade com adição)
- a 1 - a 2 ≡ b 1 - b 2 (mod n ) (compatibilidade com subtração)
- a 1 a 2 ≡ b 1 b 2 (mod n ) (compatibilidade com multiplicação)
- a k ≡ b k (mod n ) para qualquer inteiro não negativo k (compatibilidade com exponenciação)
- p ( a ) ≡ p ( b ) (mod n ) , para qualquer polinômio p ( x ) com coeficientes inteiros (compatibilidade com avaliação polinomial)
Se a ≡ b (mod n ) , então geralmente é falso que k a ≡ k b (mod n ) . No entanto, o seguinte é verdadeiro:
- Se c ≡ d (mod φ ( n )), onde φ é a função totiente de Euler , então a c ≡ a d (mod n ) - desde que a seja coprime com n .
Para o cancelamento dos termos comuns, temos as seguintes regras:
- Se a + k ≡ b + k (mod n ) , onde k é qualquer número inteiro, então a ≡ b (mod n )
- Se ka ≡ kb (mod n ) e k é primos entre si, com n , em seguida, uma ≡ b (mod n )
- Se ka ≡ kb (mod kn ) , então a ≡ b (mod n )
O inverso multiplicativo modular é definido pelas seguintes regras:
- Existência: existe um inteiro denotado a –1 tal que aa –1 ≡ 1 (mod n ) se e somente se a é coprime com n . Este inteiro a –1 é chamado de inverso multiplicativo modular de um módulo n .
- Se a ≡ b (mod n ) e a –1 existem, então a –1 ≡ b –1 (mod n ) (compatibilidade com o inverso multiplicativo, e, se a = b , unicidade módulo n )
- Se ax ≡ b (mod n ) e a é coprime com n , então a solução para esta congruência linear é dada por x ≡ a –1 b (mod n )
O multiplicativo inverso x ≡ a –1 (mod n ) pode ser eficientemente calculado resolvendo a equação de Bézout para - usando o algoritmo Euclidiano estendido .
Em particular, se p é um número primo, então a é coprime com p para todo a tal que 0 < a < p ; assim, existe um inverso multiplicativo para todo a que não é congruente com o módulo zero p .
Algumas das propriedades mais avançadas das relações de congruência são as seguintes:
- Pequeno teorema de Fermat : Se p é primo e não divide a , então a p - 1 ≡ 1 (mod p ) .
- Teorema de Euler : Se a e n são coprimos, então a φ ( n ) ≡ 1 (mod n ) , onde φ é a função totiente de Euler
- Uma consequência simples do pequeno teorema de Fermat é que se p é primo, então a −1 ≡ a p - 2 (mod p ) é o inverso multiplicativo de 0 < a < p . De forma mais geral, a partir do teorema de Euler, se a e n são coprimos, então a −1 ≡ a φ ( n ) - 1 (mod n ) .
- Outra conseqüência simples é que se a ≡ b (mod φ ( n )), onde φ é a função totiente de Euler, então k a ≡ k b (mod n ) desde que k seja coprime com n .
- Teorema de Wilson : p é primo se e somente se ( p - 1)! ≡ −1 (mod p ) .
- Teorema do resto chinês : Para qualquer a , be coprime m , n , existe um único x (mod mn ) tal que x ≡ a (mod m ) e x ≡ b (mod n ) . Na verdade, x ≡ bm n -1 m + um m -1 n (mod MN ) onde m n -1 é o inverso da m módulo n e n m -1 é o inverso de n módulo m .
- Teorema de Lagrange : A congruência f ( x ) ≡ 0 (mod p ) , onde p é primo, ef ( x ) = a 0 x n + ... + a n é um polinômio com coeficientes inteiros tais que a 0 ≠ 0 (mod p ) , tem no máximo n raízes.
- Módulo de raiz primitiva n : Um número g é um módulo de raiz primitiva n se, para cada inteiro um coprime com n , existe um inteiro k tal que g k ≡ a (mod n ) . Um módulo de raiz primitiva n existe se e somente se n for igual a 2, 4, p k ou 2 p k , onde p é um número primo ímpar ek é um inteiro positivo. Se uma raiz primitiva módulo n existe, então há exatamente φ ( φ ( n )) tais raízes primitivas, onde φ é a função de Euler de Euler.
- Resíduo quadrático : Um inteiro a é um resíduo quadrático módulo n , se existir um inteiro x tal que x 2 ≡ a (mod n ) . O critério de Euler afirma que, se p é um primo ímpar, e a não é um múltiplo de p , então a é um resíduo quadrático módulo p se e somente se
Aulas de congruência
Como qualquer relação de congruência, o módulo de congruência n é uma relação de equivalência , e a classe de equivalência do inteiro a , denotada por a n , é o conjunto {..., a - 2 n , a - n , a , a + n , a + 2 n ,…} . Esse conjunto, que consiste em todos os inteiros congruentes a um módulo n , é chamado de classe de congruência , classe de resíduo ou simplesmente resíduo do inteiro a módulo n . Quando o módulo n é conhecido a partir do contexto, esse resíduo também pode ser denotado [ a ] .
Sistemas de Resíduos
Cada classe de resíduo módulo n pode ser representada por qualquer um de seus membros, embora geralmente representemos cada classe de resíduo pelo menor inteiro não negativo que pertence a essa classe (uma vez que este é o resto apropriado que resulta da divisão). Quaisquer dois membros de diferentes classes de resíduos módulo n são incongruentes módulo n . Além disso, todo inteiro pertence a uma e apenas uma classe de resíduo módulo n .
O conjunto de inteiros {0, 1, 2,…, n - 1} é chamado de sistema de mínimo resíduo módulo n . Qualquer conjunto de n inteiros, dois dos quais não são congruentes módulo n , é chamado de sistema de resíduos completo módulo n .
O sistema de menor resíduo é um sistema de resíduo completo, e um sistema de resíduo completo é simplesmente um conjunto contendo precisamente um representante de cada classe de resíduo módulo n . Por exemplo. o módulo de sistema de menos resíduo 4 é {0, 1, 2, 3}. Alguns outros sistemas de resíduos completos módulo 4 incluem:
- {1, 2, 3, 4}
- {13, 14, 15, 16}
- {-2, -1, 0, 1}
- {−13, 4, 17, 18}
- {−5, 0, 6, 21}
- {27, 32, 37, 42}
Alguns conjuntos que não são sistemas de resíduos completos módulo 4 são:
- {−5, 0, 6, 22}, visto que 6 é congruente com 22 módulo 4.
- {5, 15}, uma vez que um sistema de resíduo completo módulo 4 deve ter exatamente 4 classes de resíduos incongruentes.
Sistemas de resíduos reduzidos
Dada a função totiente de Euler φ ( n ) , qualquer conjunto de φ ( n ) inteiros que são relativamente primos com n e mutuamente incongruentes sob o módulo n é chamado de sistema de resíduo reduzido módulo n . O conjunto {5,15} acima, por exemplo, é uma instância de um módulo de sistema de resíduo reduzido 4.
Módulo de inteiros n
O conjunto de todas as classes de congruência dos inteiros para um módulo n é chamado o anel de números inteiros módulo N , e é indicado , ou . A notação , entretanto, não é recomendada porque pode ser confundida com o conjunto de inteiros n -adic . O anel é fundamental para vários ramos da matemática (consulte § Aplicações abaixo).
O conjunto é definido para n > 0 como:
(Quando n = 0 , não é um conjunto vazio ; em vez disso, é isomórfico a , uma vez que 0 = { a } .)
Definimos adição, subtração e multiplicação pelas seguintes regras:
A verificação de que esta é uma definição adequada usa as propriedades fornecidas anteriormente.
Desta forma, torna-se um anel comutativo . Por exemplo, no ringue , temos
como na aritmética para o relógio de 24 horas.
Usamos a notação porque este é o anel quociente de pelo ideal , um conjunto contendo todos os inteiros divisíveis por n , onde é o conjunto singleton {0} . Portanto, é um campo quando é um ideal máximo (ou seja, quando n é primo).
Isso também pode ser construído a partir do grupo apenas na operação de adição. A classe de resíduos a n é o grupo coset de a no grupo quociente , um grupo cíclico .
Em vez de excluir o caso especial n = 0 , é mais útil incluir (que, como mencionado antes, é isomórfico ao anel de inteiros). Na verdade, essa inclusão é útil ao discutir as características de um anel .
O anel do módulo n de inteiros é um corpo finito se e somente se n for primo (isso garante que todo elemento diferente de zero tenha um inverso multiplicativo ). Se for uma potência primária com k > 1, existe um campo finito único (até isomorfismo) com n elementos, mas este não é , o que deixa de ser um campo porque tem divisores zero .
O subgrupo multiplicativo do módulo n de inteiros é denotado por . Este consiste em (onde a é coprime com n ), que são precisamente as classes que possuem um inverso multiplicativo. Isso forma um grupo comutativo sob multiplicação, com ordem .
Formulários
Na matemática teórica, a aritmética modular é um dos fundamentos da teoria dos números , tocando em quase todos os aspectos de seu estudo, e também é amplamente usada na teoria dos grupos , teoria dos anéis , teoria dos nós e álgebra abstrata . Na matemática aplicada, é usado em álgebra computacional , criptografia , ciência da computação , química e artes visuais e musicais .
Uma aplicação muito prática é calcular somas de verificação dentro de identificadores de número de série. Por exemplo, o International Standard Book Number (ISBN) usa aritmética do módulo 11 (para ISBN de 10 dígitos) ou módulo 10 (para ISBN de 13 dígitos) para detecção de erros. Da mesma forma, os números de contas bancárias internacionais (IBANs), por exemplo, usam 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 (um número de identificação único para cada composto químico) é um dígito de verificação , que é calculado tomando o último dígito das duas primeiras partes do número de registro CAS vezes 1, o dígito anterior vezes 2, o dígito anterior vezes 3 etc., somando tudo isso e calculando o módulo de soma 10.
Na criptografia, a aritmética modular sustenta diretamente os sistemas de chave pública , como RSA e Diffie – Hellman , e fornece campos finitos que fundamentam as curvas elípticas e é usada em uma variedade de algoritmos de chave simétrica, incluindo Advanced Encryption Standard (AES), International Data Encryption Algorithm ( IDEA) e RC4 . RSA e Diffie – Hellman usam exponenciação modular .
Na álgebra computacional, a aritmética modular é comumente usada para limitar o tamanho dos coeficientes inteiros em cálculos e dados intermediários. É usado na fatoração polinomial , um problema para o qual todos os algoritmos eficientes conhecidos usam aritmética modular. É usado pelas implementações mais eficientes do maior divisor comum polinomial , álgebra linear exata e algoritmos de base de Gröbner sobre números inteiros e racionais. Conforme postado na Fidonet na década de 1980 e arquivado no Rosetta Code , a aritmética modular foi usada para refutar a conjectura da soma dos poderes de Euler em um microcomputador Sinclair QL usando apenas um quarto da precisão inteira usada por um supercomputador CDC 6600 para refutá-la duas décadas antes por meio de uma busca de força bruta .
Na ciência da computação, a aritmética modular é frequentemente aplicada em operações bit a bit e outras operações envolvendo estruturas de dados cíclicas de largura fixa . A operação de módulo , conforme implementada em muitas linguagens de programação e calculadoras , é uma aplicação da aritmética modular frequentemente usada neste contexto. O operador lógico XOR soma 2 bits, módulo 2.
Na música, o módulo aritmético 12 é usado na consideração do sistema de temperamento igual de doze tons , onde ocorre a oitava e a equivalência enarmônica (isto é, os tons em uma proporção de 1∶2 ou 2∶1 são equivalentes, e o dó sustenido é considerado o mesmo que D- bemol ).
O método de lançar noves oferece uma verificação rápida de cálculos aritméticos decimais executados manualmente. É baseado no módulo aritmético modular 9 e, especificamente, na propriedade crucial de 10 ≡ 1 (mod 9).
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 do Juízo Final fazem uso intenso da aritmética do módulo 7.
De maneira mais geral, a aritmética modular também tem aplicação em disciplinas como direito (por exemplo, repartição ), economia (por exemplo, teoria dos jogos ) e outras áreas das ciências sociais , onde a divisão proporcional e a alocação de recursos desempenham um papel central na análise.
Complexidade computacional
Visto que a aritmética modular tem uma ampla gama de aplicações, é importante saber como é difícil resolver um sistema de congruências. Um sistema linear de congruências pode ser resolvido em tempo polinomial com uma forma de eliminação gaussiana , para detalhes veja o teorema da congruência linear . Algoritmos, como a redução de Montgomery , também existem para permitir que operações aritméticas simples, como multiplicação e exponenciação módulo n , sejam realizadas com eficiência em grandes números.
Algumas operações, como encontrar um logaritmo discreto ou uma congruência quadrática, parecem ser tão difíceis quanto a fatoração de inteiros e, portanto, são um ponto de partida para algoritmos criptográficos e criptografia . Esses problemas podem ser NP-intermediários .
Resolver um sistema de equações aritméticas modulares não lineares é NP-completo .
Implementações de exemplo
Abaixo estão três funções C razoavelmente rápidas, duas para realizar multiplicação modular e uma para exponenciação modular em inteiros sem sinal não maiores que 63 bits, sem estouro das operações transitórias.
Uma maneira algorítmica de calcular :
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
if (!((a | b) & (0xFFFFFFFFULL << 32)))
return a * b % m;
uint64_t d = 0, mp2 = m >> 1;
int i;
if (a >= m) a %= m;
if (b >= m) b %= m;
for (i = 0; i < 64; ++i)
{
d = (d > mp2) ? (d << 1) - m : d << 1;
if (a & 0x8000000000000000ULL)
d += b;
if (d >= m) d -= m;
a <<= 1;
}
return d;
}
Em arquiteturas de computador onde um formato de precisão estendido com pelo menos 64 bits de mantissa está disponível (como o tipo longo duplo da maioria dos compiladores x86 C), a seguinte rotina é, empregando o truque que, por hardware, a multiplicação de ponto flutuante resulta nos bits mais significativos do produto mantidos, enquanto a multiplicação inteira resulta nos bits menos significativos mantidos:
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
long double x;
uint64_t c;
int64_t r;
if (a >= m) a %= m;
if (b >= m) b %= m;
x = a;
c = x * b / m;
r = (int64_t)(a * b - c * m) % (int64_t)m;
return r < 0 ? r + m : r;
}
Abaixo está uma função C para realizar a exponenciação modular, que usa a função mul_mod implementada acima.
Uma maneira algorítmica de calcular :
uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m)
{
uint64_t r = m==1?0:1;
while (b > 0) {
if (b & 1)
r = mul_mod(r, a, m);
b = b >> 1;
a = mul_mod(a, a, m);
}
return r;
}
No entanto, para que todas as rotinas acima funcionem, m não deve exceder 63 bits.
Veja também
- Anel booleano
- Tampão circular
- Divisão (matemática)
- Campo finito
- Símbolo de Legendre
- Exponenciação modular
- Módulo (matemática)
- Grupo multiplicativo de módulos inteiros n
- Período Pisano (sequências de Fibonacci módulo n )
- Módulo de raiz primitiva n
- Reciprocidade quadrática
- Resíduo quadrático
- Reconstrução racional (matemática)
- Sistema de resíduos reduzidos
- Aritmética de número de série (um caso especial de aritmética modular)
- Álgebra booleana de dois elementos
- Tópicos relacionados à teoria dos grupos por trás da aritmética modular:
- Outros teoremas importantes relacionados à aritmética modular:
- Teorema de Carmichael
- Teorema do resto chinês
- Teorema de Euler
- O pequeno teorema de Fermat (um caso especial do teorema de Euler)
- Teorema de Lagrange
- Lema de quinta
Notas
Referências
- John L. Berggren. "aritmética modular" . Encyclopædia Britannica .
- Apostol, Tom M. (1976), Introdução à teoria analítica dos números , Textos de Graduação em Matemática, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929 , Zbl 0335.10001. Veja em particular os capítulos 5 e 6 para uma revisão da aritmética modular básica.
- Maarten Bullynck " Aritmética modular antes de CF Gauss. Sistematizações e discussões sobre problemas remanescentes na Alemanha do século 18 "
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein . Introdução aos algoritmos , segunda edição. MIT Press e McGraw-Hill, 2001. ISBN 0-262-03293-7 . Seção 31.3: Aritmética modular, pp. 862-868.
- Anthony Gioia , Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3 .
- Long, Calvin T. (1972). Introdução Elementar à Teoria dos Números (2ª ed.). Lexington: DC Heath and Company . LCCN 77171950 .
- Pettofrezzo, Anthony J .; Byrkit, Donald R. (1970). Elementos da teoria dos números . Englewood Cliffs: Prentice Hall . LCCN 71081766 .
- Sengadir, T. (2009). Matemática Discreta e Combinatória . Chennai, Índia: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123 .
links externos
- "Congruence" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Neste artigo de arte modular , pode-se aprender mais sobre as aplicações da aritmética modular na arte.
- Um artigo sobre aritmética modular no wiki GIMPS
- Aritmética modular e padrões em tabelas de adição e multiplicação