A criptografia RSA é um sistema de segurança digital que utiliza um par de chaves — uma pública euma privada — para proteger informações durante a transmissão. Fundamentado na complexidadematemática da fatorização de números de grande dimensão, o sistema RSA é muito utilizado paragarantir a confidencialidade e autenticidade de dados em transações online, e-mails seguros e naproteção de informações sensíveis. Sua utilidade reside na capacidade de enviar mensagens seguraspara qualquer pessoa, usando a sua chave pública, enquanto, após a encriptação, apenas o destinatário,com recurso à sua chave privada, pode decifrar e ler a mensagem. Este método de criptografia eficazcontinua a desempenhar um papel essencial na segurança da era digital.Neste estudo, inicialmente introduzimos os princípios matemáticos essenciais para a compreensãodos sistemas criptográficos. Em seguida, aborda-se a cifra RSA assim como a sua criptoanálise. Paraefeitos de comparação foram implementados os métodos clássicos: Fermat, Divisões e Euclides. Oestudo e implementação do Crivo Quadrático constitui o resultado principal desta tese de mestrado.Concluímos com uma análise comparativa das implementações dos diversos métodos mencionados anteriormente. O Crivo Quadrático, ou simplesmente chamado de QS (Quadratic Sieve), foi concebido por CarlPomerance em 1981, ao expandir as ideias anteriores dos matemáticos Kraitchik e Dixon. O QSfoi o algoritmo de fatorização mais rápido conhecido até a descoberta do Crivo de Corpo Numérico2728 Crivo Quadráticoem 1993. Ainda assim, o QS é mais eficiente, simples e rápido para números inteiros com menos de100 dígitos decimais. Trata-se de um método de fatorização de aplicação ampla, o que significa que asua velocidade de processamento é determinada exclusivamente pelo tamanho do número inteiro a serfatorado, sem considerar qualquer estrutura ou características específicas.

A criptografia RSA é um sistema de segurança digital que utiliza um par de chaves — uma pública euma privada — para proteger informações durante a transmissão. Fundamentado na complexidadematemática da fatorização de números de grande dimensão, o sistema RSA é muito utilizado paragarantir a confidencialidade e autenticidade de dados em transações online, e-mails seguros e naproteção de informações sensíveis. Sua utilidade reside na capacidade de enviar mensagens seguraspara qualquer pessoa, usando a sua chave pública, enquanto, após a encriptação, apenas o destinatário,com recurso à sua chave privada, pode decifrar e ler a mensagem. Este método de criptografia eficazcontinua a desempenhar um papel essencial na segurança da era digital.Neste estudo, inicialmente introduzimos os princípios matemáticos essenciais para a compreensãodos sistemas criptográficos. Em seguida, aborda-se a cifra RSA assim como a sua criptoanálise. Paraefeitos de comparação foram implementados os métodos clássicos: Fermat, Divisões e Euclides. Oestudo e implementação do Crivo Quadrático constitui o resultado principal desta tese de mestrado.Concluímos com uma análise comparativa das implementações dos diversos métodos mencionados anteriormente.The Quadratic Sieve, or simply QS, was conceived by Carl Pomerance in 1981 by expanding on the earlier ideas of mathematicians Kraitchik and Dixon. The QS was the fastest known factorization algorithm until the discovery of the Number Field Sieve in 1993. Even so, the QS is more efficient, simpler, and faster for integers with fewer than 100 decimal digits. It is a broadly applicable factorization method, meaning that its processing speed is determined solely by the size of the integer to be factored, without considering any specific structure or characteristics.

Dissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia