Uma forma de multiplicação modular

Um método trivial para multiplicar dois números m e n módulo um número $p$ diferente de zero e da unidade prende-se com a obtenção do produto $m\times n$ e subsequente cálculo do resto da divisão de m\times n por p. O mesmo raciocínio vale para a soma destes números sob o mesmo módulo. Esta abordagem, apesar de ser simples e directa, padece de certos defeitos quando aplicada em algoritmos de criptografia ou em algoritmos de factorização e testes de primalidade. No que concerne às exigências dos algoritmos criptográficos, onde p representa um valor extremamente elevado, o método supracitado para a obtenção do produto modular torna-se deveras moroso e várias muito mais rápidas de o realizar foram propostas.

Senti a necessidade de analisar este problema aquando do desenvolvimento de algoritmos de factorização e testes de primalidade, os quais implementei informaticamente com o auxílio de uma linguagem de programação conveniente. Durante os testes com valores relativamente elevados, constatei um defeito no algoritmo ingénuo para determinar o produto modular de dois números. As unidades aritméticas dos computadores permitem somar e multiplicar números de um conjunto finito. De facto, o maior número inteiro representável num processador actual ascende a 264 se não tivermos o sinal em conta. Se pretendermos calcular o produto de dois números superiores a 232 módulo um número igualmente grande, concluímos que a abordagem trivial não será bem sucedida uma vez que este produto excede o valor máximo 264. A soma padece do mesmo problema quando os números envolvidos são superiores a 263. Indaguei se é possível determinar a soma ou o produto modular de dois números inferiores ao módulo recorrendo unicamente a operações aritméticas com resultados numéricos que não acresçam o valor do módulo.

Uma vez que a discussão do processo é demasiado longa, coloquei-a no ficheiro Uma forma de multiplicação modular.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Matemática, Sem categoria com as etiquetas , , , . ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s