Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Algoritmo de Shor e sua aplicação à fatoração de números inteiros

Adriana Xavier Freitas

Published Feb 18, 2010• 0 citations
OpenAlex

Abstract

O algoritmo de Shor é um algoritmo quântico que encontra com alta probabilidade a ordem de um elemento $x \\in Z_{N}^{*}$. Uma de suas aplicações é a construção de um algoritmo que encontra fatores de N. Nos capítulos iniciais abordaremos ferramentas necessárias para o entendimento do algoritmo de Shor, tais como: aritmética modular, algoritmos, frações contínuas, conceitos introdutórios de computação quântica e transformada quântica de Fourier. Nos capítulos seguintes apresentamos o algoritmo de Shor e sua aplicação á fatoração de números inteiros.

Related papers

Um estudo passo a passo dos algoritmos de Grover e Shor

Luciano Alves Vieira, Clarice Dias de Albuquerque

Um estudo passo a passo dos algoritmos de Grover e Shor A step-by-step study of Grover and Shor algorithmsResumo Os algoritmos de Grover e de Shor são duas das principais descobertas da computação quântica no início das pesquisas nessa área.O primeiro é um algoritmo de busca com um ganho de velocidade significativo em relação aos algoritmos clássicos e com grande aplicação na resolução de diversos outros problemas.O segundo é capaz de resolver o problema da fatoração de um número C em tempo polinomial, o que foi responsável por um grande impulso na pesquisa em computação e criptografia quântica.Neste trabalho de Iniciação Científica apresentamos os algoritmos quânticos de Grover e Shor, amplamente utilizados na computação quântica, com uma proposta original focada nos estados quânticos obtidos após cada passo na evolução do circuito.Dessa forma, exercita-se a aplicação das portas quânticas e a percepção das propriedades quânticas, bem como o funcionamento desses dois algoritmos.No circuito de Grover destacamos a fundamental propriedade de emaranhamento quântico que permite executar tarefas de processamento de informação.

C Q D - Revista Eletrônica Paulista de Matemática•Dec 1, 2020•1 citation

Ataques quânticos e os criptossistemas de McEliece

Jorge Manuel Tavares Brandão

0 algoritmo de Shor e a evolução da computação quântica trouxeram grandes ameaças à segurança dos criptossistemas atuais. Pela necessidade de se encontrar novas alternativas, surgiu a criptografia pós-quântica. Esta dissertação pode ser dividida em três partes principais. Na primeira apresentamos alguns elementos de teoria dos números e descrevemos um criptossistema clássico, o RSA, cuja segurança pode ser facilmente quebrada recorrendo a ataques quânticos. Na segunda parte descrevemos a implementação do algoritmo de Shor, que é um ataque a esse e a todos os criptossistemas cuja segurança reside no problema da fatorização ou no problema do logaritmo discreto. Na implementação deste algoritmo minimizámos o número de qubits necessários. Para isso, utilizámos transformadas de Fourier quânticas para realizar operações como a adição, a multiplicação e a exponenciação modular. Assim, segundo a nossa abordagem, precisámos de apenas Li + 2L2 + 3 qubits, para implementar o algoritmo de Shor, ou seja, para encontrar o período da função /(x) = ax mod N, onde Li corresponde ao número de qubits necessários para representar x tal que N2 < 2L1 < 2N2 e L2 corresponde ao número de qubits necessários para representar N. Por fim, na última parte desta dissertação, apresentaremos elementos da criptografia pós-quântica, em particular, um protocolo proposto por nós. Este é uma nova variante do criptossistema de McEliece, no qual se propõe o uso de códigos convolucionais em vez do uso de códigos de bloco. Assim, a parte codificadora da nossa chave pública, que denotaremos por G'(D), será ela própria convolucional. Ao estudarmos várias possibilidades de ataques para este criptossistema, verificámos que, em comparação com as restantes variantes, para uma chave pública menor conseguimos ter um fator de trabalho muito maior, o que se traduz numa maior segurança

•Jul 31, 2018•0 citations

Simulação de um Algoritmo quântico, com Transformadas de Fourier quânticas

André Paulo Pires Miranda Ferreira da Silva

Computação quântica é uma área de grande desenvolvimento hoje em dia e isso traz uma necessidade para desenvolver hardware e software. Uma vez que o hardware disponível é muito pouco e o software precisa de ser testado, existe uma necessidade de uma boa plataforma para testar as soluções de software. Simular um computador quântico num computador clássico não é ideal, contudo é uma resposta viável a esta necessidade, para um pequeno número de qubits. Além disso, os computadores quânticos necessitam dos computadores clássicos de forma a criar um sistema real prático, isto apresenta-se como uma excelente oportunidade para testar técnicas de programação clássica para melhorar a programação quântica. Esta tese propõe o uso de programação clássica para melhorar a implementação de um algoritmo de adição modular usando transformadas de Fourier quânticas. Os principais objectivos deste trabalho são: simular um circuito quântico; testar um algoritmo quântico e compará-lo com o seu equivalente clássico; implementar o algoritmo de adição modular, usando as capacidades de aceleração de computação das transformadas de Fourier quânticas e optimizá-lo; Testar e implementar códigos quânticos de correcção de erros; fazer um teste num computador quântico real.De forma a testar a linguagem e comparar um algoritmo quântico com um clássico, fez-se um teste ao algoritmo de Shor que está disponível de raiz na plataforma liquid. Apesar do algoritmo de Shor ter, teoricamente, uma dependência de tipo polinomial com a dimensão do problema, os testes realizados mostraram que o tempo de computação tem um comportamento exponencial. Simular um algoritmo quântico num computador clássico requer tempo de computação que cresce de forma exponencial, pois é necessário armazenar e processar todos os estados do sistema, que é um espaço de Hilbert de dimensão 2^n.O algoritmo de adição modular usando transformadas de Fourier quânticas foi implementado na plataforma liquid. Seguidamente fizeram-se melhorias e optimizações. O número de operações teórico é O(n^2). Contudo, depois de fazer melhorias ao circuito, removendo gates desnecessárias para casos específicos, o número de operações passa a ter um valor mínimo de Omega(n). Com este tipo de alterações o sistema pode apresentar melhorias no que respeito ao tempo de simulação até um factor de ordem 10. Isto mostra que programar um algoritmo quântico tendo em conta casos específicos pode melhorar imenso o desempenho da simulação.Os códigos de correção de erros quânticos foram implementados num circuito simples, com as ferramentas disponíveis na plataforma liquid, e obteve-se um sistema que consegue lidar com erros com probabilidade inferior ou igual a 2%, com uma taxa de sucesso na sua correção de 95%. Contudo são necessários circuitos muito grandes, pouco exequíveis.A plataforma disponibilizada pela IBM para fazer testes num computador quântico real, foi utilizada para testar o algoritmo de adição modular e adição normal (com carry bit). Uma vez que esta plataforma tem um número limitado de gates, reforça a ideia de que se deve otimizar os algoritmos tendo em conta casos particulares. Os resultados destes testes mostram também que é importante utilizar correcção de erros quânticos, mas para que isso seja viável é necessário que haja mais qubits disponíveis ou outro tipo de códigos.

•Oct 10, 2018•0 citations

Computação quântica: comparativo dos algoritmos de Shor e de Fermat

Silva, Silviane

Tanto um computador clássico quanto um computador quântico fazem uso de algoritmos para realização de suas operações. Este trabalho se propõe a apresentar de forma simplificada uma breve introdução à computação quântica, compará-la com a computação clássica e mostrar o desempenho do algoritmo de Shor em um software desenvolvido para este trabalho, para o cálculo dos fatores coprimos de um número, em relação ao algoritmo de Fermat utilizado na computação clássica, demonstrando os resultados encontrados.

•Jan 1, 2014•0 citations

ALGORITMO DE SHOR

Marcelo Gabriel Batista, Antonio Carlos Amaro de Faria

Este artigo explora a intersecção fascinante entre a mecânica quântica e a computação, dois campos aparentemente distintos que se entrelaçam em uma simbiose surpreendente. Ao destacar os princípios fundamentais da mecânica quântica, como superposição e emaranhamento, este estudo lança luz sobre sua aplicação inovadora na computação quântica. Em particular, focamos no algoritmo Shor, uma conquista marcante neste campo emergente. O algoritmo Shor demonstra a capacidade única da computação quântica de resolver rapidamente problemas que seriam intratáveis para computadores clássicos. Exploramos como o algoritmo utiliza os princípios quânticos de superposição e emaranhamento para fatorar números inteiros em seus primos constituintes com eficiência exponencialmente superior aos métodos clássicos. Além disso, discutimos as implicações profundas desse avanço, desde a criptografia até a modelagem de sistemas complexos. Ao destacar o potencial revolucionário da computação quântica, este artigo lança luz sobre o futuro promissor de uma nova era de computação, onde os limites tradicionais são desafiados e novas fronteiras são abertas.

Revista Contemporânea•Jul 4, 2024•0 citations

ALGORITMOS QUÂNTICOS: Da lógica clássica à computação quântica

Jaconaazar Souza Silva

Algoritmos Quânticos: Da lógica clássica à computação quântica apresenta uma introdução progressiva, técnica e computacional aos fundamentos e aos principais algoritmos da computação quântica. A obra parte dos conceitos clássicos de algoritmo, complexidade computacional, teoria dos números e álgebra linear para construir, passo a passo, a compreensão de qubits, superposição, medição, interferência, portas quânticas, circuitos e emaranhamento. Ao longo do livro são desenvolvidos algoritmos fundamentais como Deutsch, Deutsch–Jozsa, Simon e Grover, avançando para a Transformada Quântica de Fourier (QFT), estimação quântica de fase e o algoritmo de Shor. A obra também discute amplificação de amplitude, criptografia pós-quântica, computação híbrida quântico-clássica, VQE, QAOA, barren plateaus, ruído, correção e mitigação de erros, além dos diferentes significados de vantagem quântica e dos limites atuais da tecnologia. Uma parte substancial do livro é dedicada à implementação prática com Python e Qiskit, incluindo preparação e medição de estados, estados de Bell, circuitos de Grover, QFT, estimação de fase, demonstrações de Shor, simulação local, transpilação e execução em processadores quânticos (QPUs). O texto procura distinguir rigorosamente vantagem algorítmica teórica, vantagem experimental e utilidade prática, evitando interpretações excessivamente simplificadas da computação quântica. O objetivo é oferecer uma ponte entre Ciência da Computação clássica e computação quântica para estudantes, desenvolvedores, pesquisadores e leitores interessados em compreender não apenas como os algoritmos quânticos funcionam, mas também quando, por que e sob quais condições eles podem oferecer vantagens computacionais. Palavras-chave Computação quântica; Algoritmos quânticos; Quantum computing; Quantum algorithms; Qubits; Circuitos quânticos; Quantum circuits; Qiskit; Algoritmo de Grover; Grover's algorithm; Algoritmo de Shor; Shor's algorithm; Transformada Quântica de Fourier; Quantum Fourier Transform; Estimação quântica de fase; Quantum Phase Estimation; VQE; QAOA; Computação híbrida quântico-clássica; Criptografia pós-quântica; Complexidade computacional; Emaranhamento quântico; Amplificação de amplitude; Programação quântica.

•Sep 3, 2026•0 citations
O algoritmo de Shor é um algoritmo quântico que encontra com alta probabilidade a ordem de um elemento xinZN∗x \\in Z_{N}^{*}xinZN∗​. Uma de suas aplicações é a construção de um algoritmo que encontra fatores de N. Nos capítulos iniciais abordaremos ferramentas necessárias para o entendimento do algoritmo de Shor, tais como: aritmética modular, algoritmos, frações contínuas, conceitos introdutórios de computação quântica e transformada quântica de Fourier. Nos capítulos seguintes apresentamos o algoritmo de Shor e sua aplicação á fatoração de números inteiros.
Um estudo passo a passo dos algoritmos de Grover e Shor A step-by-step study of Grover and Shor algorithmsResumo Os algoritmos de Grover e de Shor são duas das principais descobertas da computação quântica no início das pesquisas nessa área.O primeiro é um algoritmo de busca com um ganho de velocidade significativo em relação aos algoritmos clássicos e com grande aplicação na resolução de diversos outros problemas.O segundo é capaz de resolver o problema da fatoração de um número C em tempo polinomial, o que foi responsável por um grande impulso na pesquisa em computação e criptografia quântica.Neste trabalho de Iniciação Científica apresentamos os algoritmos quânticos de Grover e Shor, amplamente utilizados na computação quântica, com uma proposta original focada nos estados quânticos obtidos após cada passo na evolução do circuito.Dessa forma, exercita-se a aplicação das portas quânticas e a percepção das propriedades quânticas, bem como o funcionamento desses dois algoritmos.No circuito de Grover destacamos a fundamental propriedade de emaranhamento quântico que permite executar tarefas de processamento de informação.
0 algoritmo de Shor e a evolução da computação quântica trouxeram grandes ameaças à segurança dos criptossistemas atuais. Pela necessidade de se encontrar novas alternativas, surgiu a criptografia pós-quântica. Esta dissertação pode ser dividida em três partes principais. Na primeira apresentamos alguns elementos de teoria dos números e descrevemos um criptossistema clássico, o RSA, cuja segurança pode ser facilmente quebrada recorrendo a ataques quânticos. Na segunda parte descrevemos a implementação do algoritmo de Shor, que é um ataque a esse e a todos os criptossistemas cuja segurança reside no problema da fatorização ou no problema do logaritmo discreto. Na implementação deste algoritmo minimizámos o número de qubits necessários. Para isso, utilizámos transformadas de Fourier quânticas para realizar operações como a adição, a multiplicação e a exponenciação modular. Assim, segundo a nossa abordagem, precisámos de apenas Li + 2L2 + 3 qubits, para implementar o algoritmo de Shor, ou seja, para encontrar o período da função /(x) = ax mod N, onde Li corresponde ao número de qubits necessários para representar x tal que N2 < 2L1 < 2N2 e L2 corresponde ao número de qubits necessários para representar N. Por fim, na última parte desta dissertação, apresentaremos elementos da criptografia pós-quântica, em particular, um protocolo proposto por nós. Este é uma nova variante do criptossistema de McEliece, no qual se propõe o uso de códigos convolucionais em vez do uso de códigos de bloco. Assim, a parte codificadora da nossa chave pública, que denotaremos por G'(D), será ela própria convolucional. Ao estudarmos várias possibilidades de ataques para este criptossistema, verificámos que, em comparação com as restantes variantes, para uma chave pública menor conseguimos ter um fator de trabalho muito maior, o que se traduz numa maior segurança
Computação quântica é uma área de grande desenvolvimento hoje em dia e isso traz uma necessidade para desenvolver hardware e software. Uma vez que o hardware disponível é muito pouco e o software precisa de ser testado, existe uma necessidade de uma boa plataforma para testar as soluções de software. Simular um computador quântico num computador clássico não é ideal, contudo é uma resposta viável a esta necessidade, para um pequeno número de qubits. Além disso, os computadores quânticos necessitam dos computadores clássicos de forma a criar um sistema real prático, isto apresenta-se como uma excelente oportunidade para testar técnicas de programação clássica para melhorar a programação quântica. Esta tese propõe o uso de programação clássica para melhorar a implementação de um algoritmo de adição modular usando transformadas de Fourier quânticas. Os principais objectivos deste trabalho são: simular um circuito quântico; testar um algoritmo quântico e compará-lo com o seu equivalente clássico; implementar o algoritmo de adição modular, usando as capacidades de aceleração de computação das transformadas de Fourier quânticas e optimizá-lo; Testar e implementar códigos quânticos de correcção de erros; fazer um teste num computador quântico real.De forma a testar a linguagem e comparar um algoritmo quântico com um clássico, fez-se um teste ao algoritmo de Shor que está disponível de raiz na plataforma liquid. Apesar do algoritmo de Shor ter, teoricamente, uma dependência de tipo polinomial com a dimensão do problema, os testes realizados mostraram que o tempo de computação tem um comportamento exponencial. Simular um algoritmo quântico num computador clássico requer tempo de computação que cresce de forma exponencial, pois é necessário armazenar e processar todos os estados do sistema, que é um espaço de Hilbert de dimensão 2^n.O algoritmo de adição modular usando transformadas de Fourier quânticas foi implementado na plataforma liquid. Seguidamente fizeram-se melhorias e optimizações. O número de operações teórico é O(n^2). Contudo, depois de fazer melhorias ao circuito, removendo gates desnecessárias para casos específicos, o número de operações passa a ter um valor mínimo de Omega(n). Com este tipo de alterações o sistema pode apresentar melhorias no que respeito ao tempo de simulação até um factor de ordem 10. Isto mostra que programar um algoritmo quântico tendo em conta casos específicos pode melhorar imenso o desempenho da simulação.Os códigos de correção de erros quânticos foram implementados num circuito simples, com as ferramentas disponíveis na plataforma liquid, e obteve-se um sistema que consegue lidar com erros com probabilidade inferior ou igual a 2%, com uma taxa de sucesso na sua correção de 95%. Contudo são necessários circuitos muito grandes, pouco exequíveis.A plataforma disponibilizada pela IBM para fazer testes num computador quântico real, foi utilizada para testar o algoritmo de adição modular e adição normal (com carry bit). Uma vez que esta plataforma tem um número limitado de gates, reforça a ideia de que se deve otimizar os algoritmos tendo em conta casos particulares. Os resultados destes testes mostram também que é importante utilizar correcção de erros quânticos, mas para que isso seja viável é necessário que haja mais qubits disponíveis ou outro tipo de códigos.
Tanto um computador clássico quanto um computador quântico fazem uso de algoritmos para realização de suas operações. Este trabalho se propõe a apresentar de forma simplificada uma breve introdução à computação quântica, compará-la com a computação clássica e mostrar o desempenho do algoritmo de Shor em um software desenvolvido para este trabalho, para o cálculo dos fatores coprimos de um número, em relação ao algoritmo de Fermat utilizado na computação clássica, demonstrando os resultados encontrados.
Este artigo explora a intersecção fascinante entre a mecânica quântica e a computação, dois campos aparentemente distintos que se entrelaçam em uma simbiose surpreendente. Ao destacar os princípios fundamentais da mecânica quântica, como superposição e emaranhamento, este estudo lança luz sobre sua aplicação inovadora na computação quântica. Em particular, focamos no algoritmo Shor, uma conquista marcante neste campo emergente. O algoritmo Shor demonstra a capacidade única da computação quântica de resolver rapidamente problemas que seriam intratáveis para computadores clássicos. Exploramos como o algoritmo utiliza os princípios quânticos de superposição e emaranhamento para fatorar números inteiros em seus primos constituintes com eficiência exponencialmente superior aos métodos clássicos. Além disso, discutimos as implicações profundas desse avanço, desde a criptografia até a modelagem de sistemas complexos. Ao destacar o potencial revolucionário da computação quântica, este artigo lança luz sobre o futuro promissor de uma nova era de computação, onde os limites tradicionais são desafiados e novas fronteiras são abertas.
Algoritmos Quânticos: Da lógica clássica à computação quântica apresenta uma introdução progressiva, técnica e computacional aos fundamentos e aos principais algoritmos da computação quântica. A obra parte dos conceitos clássicos de algoritmo, complexidade computacional, teoria dos números e álgebra linear para construir, passo a passo, a compreensão de qubits, superposição, medição, interferência, portas quânticas, circuitos e emaranhamento. Ao longo do livro são desenvolvidos algoritmos fundamentais como Deutsch, Deutsch–Jozsa, Simon e Grover, avançando para a Transformada Quântica de Fourier (QFT), estimação quântica de fase e o algoritmo de Shor. A obra também discute amplificação de amplitude, criptografia pós-quântica, computação híbrida quântico-clássica, VQE, QAOA, barren plateaus, ruído, correção e mitigação de erros, além dos diferentes significados de vantagem quântica e dos limites atuais da tecnologia. Uma parte substancial do livro é dedicada à implementação prática com Python e Qiskit, incluindo preparação e medição de estados, estados de Bell, circuitos de Grover, QFT, estimação de fase, demonstrações de Shor, simulação local, transpilação e execução em processadores quânticos (QPUs). O texto procura distinguir rigorosamente vantagem algorítmica teórica, vantagem experimental e utilidade prática, evitando interpretações excessivamente simplificadas da computação quântica. O objetivo é oferecer uma ponte entre Ciência da Computação clássica e computação quântica para estudantes, desenvolvedores, pesquisadores e leitores interessados em compreender não apenas como os algoritmos quânticos funcionam, mas também quando, por que e sob quais condições eles podem oferecer vantagens computacionais. Palavras-chave Computação quântica; Algoritmos quânticos; Quantum computing; Quantum algorithms; Qubits; Circuitos quânticos; Quantum circuits; Qiskit; Algoritmo de Grover; Grover's algorithm; Algoritmo de Shor; Shor's algorithm; Transformada Quântica de Fourier; Quantum Fourier Transform; Estimação quântica de fase; Quantum Phase Estimation; VQE; QAOA; Computação híbrida quântico-clássica; Criptografia pós-quântica; Complexidade computacional; Emaranhamento quântico; Amplificação de amplitude; Programação quântica.