Análise Assintótica de Abordagens Propostas para a Resolução de Sistemas de Congruências Lineares
Abstract
A Teoria dos Números é um ramo da Matemática que estuda as propriedades e relações entre os números inteiros [2], com aplicações significativas em Ciência da Computação, como a cifração e decifração de blocos do algoritmo criptográfico RSA. Nesse contexto, as congruências lineares desempenham um papel crucial, especialmente na resolução de sistemas de equações modulares. O Teorema Chinês do Resto (TCR) é uma ferramenta para a resolução de tais sistemas, mas sua eficiência computacional varia conforme a implementação. A análise assintótica provê ferramentas e técnicas matemáticas para analisar o desempenho de algoritmos [1]. Desse modo, pode-se determinar se uma implementação computacional oferece uma solução correta em tempo viável de execução conforme o crescimento do tamanho da entrada. Este trabalho propõe uma análise assintótica de diferentes abordagens para a resolução de sistemas de congruências lineares, com foco na otimização do tempo de execução. [...]
Downloads
References
T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Introduction To Algorithms. 2a. ed. MIT Press, 2001. isbn: 0262032937.
G. H. Hardy, E. M. Wright, D. R. Heath-Brown e J. Silverman. An Introduction to the Theory of Numbers. 6a. ed. USA: OUP Oxford, 2008. isbn: 9780199219865.
A. C. Q. Rosa, F. C. G. Manso e W. J. Corrêa. “Uma abordagem matemática para a otimização do custo computacional do Teorema Chinês do Resto”. Em: Anais da XI Bienal da Matemática. UFSCar, São Carlos, SP, 2024.
A. C. Q. Rosa, F. C. G. Manso e W. J. Corrêa. “Uma nova perspectiva para o Algoritmo de Euclides: Uma abordagem computacional para o cálculo dos coeficientes da Relação de Bézout”. Em: Anais do XIII Seminário de Extensão e Inovação e XXVIII Seminário de Iniciação Científica e Tecnológica da UTFPR. UTFPR, Ponta Grossa, PR, 2023.
