Calculadora do teorema chinês do resto
Conte um monte de coisas de três em três e sobram 2, de cinco em cinco sobram 3, de sete em sete sobram 2: são 23, ou 128, ou 233, uma resposta a cada 105. É o problema do Sunzi Suanjing que deu nome ao teorema chinês do resto. Escreva qualquer sistema de congruências x ≡ a (mod n), com tantas equações e números tão grandes quanto quiser, e veja a resposta, a resolução com os seus números e uma imagem de porque funciona. Quando as equações não podem verificar-se todas, a calculadora indica as duas que entram em conflito e mostra porquê. Escreva as equações x ≡ a (mod n), uma por linha: a é o resto e n o módulo. Acrescente uma linha com Adicionar equação, ou com Enter no último módulo, e retire-a com ×. Funcionam números inteiros até 200 algarismos, e a pode ser negativo. Ou escolha um exemplo resolvido. Os mosaicos mostram a menor solução e de quanto em quanto se repete; por baixo aparecem as primeiras soluções positivas e uma verificação de cada equação. A imagem marca os números que satisfazem cada equação, e a coluna em que todas as linhas têm uma marca é a solução; a tabela de restos mostra duas equações ao mesmo tempo. A resolução é escrita com os seus números, pela construção clássica ou por substituição.
Como funciona
- Escreva as equações x ≡ a (mod n), uma por linha, ou escolha um exemplo resolvido como o problema de Sunzi, o cesto de ovos ou o período juliano.
- Leia a menor solução, o módulo com que se repete e as primeiras soluções positivas, cada uma verificada em todas as equações.
- Siga a resolução passo a passo, pela construção ou por substituição, e mude a imagem entre a reta numérica e a tabela de restos.
Como funciona a construção
Quando nenhum par de módulos tem um fator comum, a solução pode ser construída diretamente. Multiplique os módulos: para o problema de Sunzi, N = 3 × 5 × 7 = 105. Para cada equação tome Nᵢ = N / nᵢ, múltiplo de todos os outros módulos: 35, 21 e 15. Depois encontre o inverso yᵢ de Nᵢ mod nᵢ com o algoritmo de Euclides estendido: 35 deixa resto 2 na divisão por 3, e 2 × 2 = 4 ≡ 1 (mod 3), por isso y₁ = 2; 21 e 15 deixam resto 1, por isso os seus inversos são 1. Então x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, e 233 mod 105 = 23. Cada termo encaixa na sua própria equação e é múltiplo dos outros módulos, por isso a soma encaixa em todas.
Quando os módulos têm um fator comum
Um sistema cujos módulos têm fatores comuns também pode ter solução. Duas equações x ≡ a (mod m) e x ≡ b (mod n) podem verificar-se ao mesmo tempo exatamente quando a − b é múltiplo de gcd(m, n), e a solução repete-se então a cada lcm(m, n) em vez de a cada m × n. Dois autocarros que partem aos minutos 5 e 11, de 12 em 12 e de 18 em 18 minutos, encontram-se ao minuto 29 e depois de 36 em 36 minutos, porque 11 − 5 = 6 é múltiplo de gcd(12, 18) = 6. Mas x ≡ 1 (mod 4) e x ≡ 4 (mod 6) nunca se podem verificar juntas: a primeira torna x ímpar e a segunda par. Um sistema inteiro tem solução exatamente quando cada par das suas equações tem, e é assim que a calculadora encontra as duas que entram em conflito.
Perguntas frequentes
O que diz o teorema chinês do resto?
Se nenhum par dos módulos n₁, n₂, … tiver um fator comum, então para quaisquer restos a₁, a₂, … existe exatamente um x de 0 a N − 1 com x ≡ aᵢ (mod nᵢ) para cada i, onde N é o produto dos módulos. Qualquer outra solução difere dela por um múltiplo de N: para o problema de Sunzi, as soluções são 23, 128, 233 e assim por diante, uma a cada 105.
Porque se chama chinês?
O mais antigo problema conhecido deste tipo está no Sunzi Suanjing, um livro de aritmética chinês escrito entre os séculos III e V: contadas de três em três, de cinco em cinco e de sete em sete, umas coisas deixam restos 2, 3 e 2. Qin Jiushao deu um método geral para estes problemas em 1247, e Carl Friedrich Gauss enunciou o teorema na sua forma moderna em 1801.
E se os módulos não forem primos entre si?
Então pode não haver solução, e quando há, repete-se a cada mínimo múltiplo comum dos módulos em vez de a cada produto. Duas equações concordam quando os seus restos coincidem módulo o gcd dos seus módulos. O enigma dos ovos usa 2, 3, 4, 5, 6 e 7, que têm fatores comuns, e mesmo assim tem solução: 301, que se repete a cada 420.
Como é que o RSA usa o teorema chinês do resto?
Decifrar uma mensagem RSA é calcular c^d mod n, onde n = p × q. É mais rápido calcular c^d mod p e c^d mod q em separado, com o expoente reduzido mod p − 1 e q − 1, e juntar os dois resultados com o teorema. Com números com metade do comprimento, cada uma das duas potências custa cerca de um oitavo do trabalho, por isso a decifração é cerca de quatro vezes mais rápida, e a maior parte do software RSA faz assim.
Que tamanho podem ter os números?
Até 20 equações, com números até 200 algarismos cada. A calculadora trabalha com números inteiros exatos no seu navegador, por isso a resposta é exata por mais longa que seja, e nada é enviado para lado nenhum.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor