Implementação eficiente de algoritmos para teste de primalidade

Abstract

O desenvolvimento da criptografia, em especial a criptografia de chave assimétrica, foi fator determinante para o crescimento e popularização das redes de computadores. Foi responsável pela viabilização de demandas como comércio e correio eletrônicos, assinaturas e certificações digitais. O uso adequado de técnicas criptográficas requer o desenvolvimento de aplicações eficientes que sejam capazes de executar em diversos tipos de dispositivos que cada vez mais se incorporam à vida das pessoas. A geração de chaves criptográficas é uma operação não só crítica quanto à segurança, mas também de alto custo computacional. Este trabalho tem o intuito de estudar sistemas criptográficos, conceitos teóricos e teste de primalidade, elemento que compõe o núcleo do processo de geração de chaves. É dado enfoque na implementação, otimização e análise de desempenho do Teste de Frobenius Quadrático Simplificado, um teste de primalidade de 2005 e pouco explorado. Os resultados atingidos são positivos quanto à viabilidade da redução do custo computacional dessas operações. ____________________________________________________________________________ ABSTRACT

The development of cryptography, public key cryptography in particular, was a crucial factor responsible for the growth and popularization of computer networks. It was responsible for appearance of demands as email, e-commerce, digitals signature and certification. The proper use of cryptographic techniques requires the development of efficient applications capable of running in all kind of devices witch more and more incorporates people's lives. The generation of cryptographic keys is not only a critical security operation but also a have high computational cost. This project has the goal of studying cryptosystems and their theoretical basis and primality test, the core element of the key generation process. It has an especial approach on implementing, optimizing and performance analysis of Simplified Frobenius Quadratic Test, a primality test from 2005 and under explored. The achieved results are positives about the feasibility of reducing the computational cost of operation.