Defesa de Proposta de Tese de Doutorado de Fábio Gomes dos Santos, em 02/04/24, às 10:00h, na sala 310 do Instituto de Computação
Análise de Algoritmos Quânticos para Solução do Logaritmo Discreto Através de Simulações
Resumo:
Com a evolução da Computação Quântica e o surgimento de algoritmos desenvolvidos para esse novo paradigma, evidenciou-se que através de alguns deles seria possível, por exemplo, ganhos exponenciais em complexidade de tempo. Esse é o caso do algoritmo de Shor para a solução do problema do logaritmo discreto. Conseguir executar este algoritmo em tempo polinomial tem um impacto muito relevante no fluxo de troca segura de informações entre pessoas e instituições. Esse impacto é devido ao fato desse problema matemático ser a base para boa parte dos protocolos criptográficos utilizados hoje em dia. Dada esta relevância, julgamos importante o estudo mais aprofundado da solução para o problema do logaritmo discreto. Dessa forma, nossa proposta de trabalho é prover um simulador que execute os passos o mais próximo possível do algoritmo original de Shor para solução do problema do logaritmo discreto. Isso nos permite propor ajustes visando melhorias ou até mesmo uma nova abordagem e conseguir fazer comparações com o algoritmo original.
Abstract:
With the evolution of Quantum Computing and the emergence of algorithms developed for this new paradigm, it became clear that through some of them it would be possible, for example, to achieve exponential gains in time complexity for some practical algorithms. This is the case of Shor’s algorithm for solving the discrete logarithm problem. Being able to execute this algorithm in polynomial time has a very relevant impact on the flow of secure information exchange between people and institutions. This impact is due to the fact that this mathematical problem is the basis for much of the cryptography stack used today. Given this relevance, we believe it is important to further study the solution to the discrete logarithm problem. Therefore, our work proposal is to provide a simulator that performs the steps as close as possible to Shor’s original algorithm for solving the discrete logarithm problem. This allows us to propose adjustments aimed at improvements or even a new approach and to be able to make comparisons with the original algorithm.
Banca examinadora:
Prof. Luis Antonio Brasil Kowada, UFF – Presidente
Prof. Luís Felipe Ignácio Cunha, UFF
Prof. Uéverton dos Santos Souza, UFF
Profa. Celina Miraglia Herrera de Figueiredo, UFRJ