{"id":470,"date":"2026-03-03T22:42:32","date_gmt":"2026-03-03T22:42:32","guid":{"rendered":"https:\/\/luizlohn.com.br\/blog\/?p=470"},"modified":"2026-03-05T22:12:57","modified_gmt":"2026-03-05T22:12:57","slug":"shors-algorithm-na-pratica-como-quebrar-rsa-na-era-quantica","status":"publish","type":"post","link":"https:\/\/luizlohn.com.br\/blog\/shors-algorithm-na-pratica-como-quebrar-rsa-na-era-quantica\/","title":{"rendered":"Shor\u2019s Algorithm na Pr\u00e1tica: Como Quebrar RSA na Era Qu\u00e2ntica"},"content":{"rendered":"\n<p id=\"ember63\">N\u00e3o costumo publicar aqui sobre computa\u00e7\u00e3o qu\u00e2ntica, mas faz parte do estudo! Ent\u00e3o bora l\u00e1!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember64\">Shor\u2019s Algorithm na Pr\u00e1tica: Como Quebrar RSA na Era Qu\u00e2ntica<\/h3>\n\n\n\n<p id=\"ember65\">O <strong>Algoritmo de Shor<\/strong> n\u00e3o \u00e9 mais apenas teoria \u2014 \u00e9 uma amea\u00e7a matem\u00e1tica real para qualquer algoritmo baseado na dificuldade de fatora\u00e7\u00e3o de inteiros ou logaritmos discretos, como <strong>RSA<\/strong>, <strong>ECC<\/strong> e <strong>DH<\/strong>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember66\">Passo a Passo de Como o Shor\u2019s Algorithm Quebra RSA<\/h3>\n\n\n\n<p id=\"ember67\">Vamos entender matematicamente como o algoritmo funciona:<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember68\">1\ufe0f\u20e3 Problema de Fatora\u00e7\u00e3o no RSA<\/h3>\n\n\n\n<p id=\"ember69\">O RSA \u00e9 baseado em:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>N = p \u22c5 q \u2192 Produto de dois n\u00fameros primos grandes.<\/li>\n\n\n\n<li>A seguran\u00e7a reside no fato de que, dado <strong><em>N<\/em><\/strong>, encontrar <strong><em>p<\/em><\/strong> e <strong><em>q<\/em><\/strong> \u00e9 extremamente dif\u00edcil.<\/li>\n<\/ul>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>Exemplo cl\u00e1ssico:<\/p>\n<\/blockquote>\n\n\n\n<p id=\"ember72\"><strong><em>N<\/em><\/strong>=15 \u2192 Fatores: 333 e 555<\/p>\n\n\n\n<p id=\"ember73\">Agora, tente fazer isso com:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><strong><em>N<\/em><\/strong>=30917491529933431 (um n\u00famero de 50 bits)<\/p>\n<\/blockquote>\n\n\n\n<p id=\"ember75\">Ou na pr\u00e1tica do RSA:<\/p>\n\n\n\n<p id=\"ember76\"><strong><em>N<\/em><\/strong> de 2048 bits.<\/p>\n\n\n\n<p id=\"ember77\">Computadores cl\u00e1ssicos levariam milh\u00f5es de anos. O <strong>Shor\u2019s Algorithm<\/strong> resolve isso em tempo polinomial.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember78\">2\ufe0f\u20e3 Fluxo Matem\u00e1tico do Shor<\/h3>\n\n\n\n<p id=\"ember79\"><strong>Entrada:<\/strong> Um inteiro NN para fatora\u00e7\u00e3o.<\/p>\n\n\n\n<p id=\"ember80\"><strong>Etapas principais:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Escolher um inteiro aleat\u00f3rio aa, tal que 1 &lt; a &lt; N. &#8211; <\/strong>Verificar se gcd(a,N)\u22601. Se sim, j\u00e1 achamos um divisor.<\/li>\n\n\n\n<li><strong>Executar a busca de per\u00edodo (Quantum Period Finding) da fun\u00e7\u00e3o:<\/strong><\/li>\n<\/ol>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/media.licdn.com\/dms\/image\/v2\/D4D12AQHolvM9XddRhA\/article-inline_image-shrink_400_744\/B4DZd51XtLGkAc-\/0\/1750095723768?e=1774483200&amp;v=beta&amp;t=C5O3GifLmrvNaLTOlzqNT0rDyqnRF_1C8ANLkHrrCZs\" alt=\"Conte\u00fado do artigo\"\/><\/figure>\n\n\n\n<p id=\"ember83\">\u2192 Achar o menor inteiro <strong><em>r<\/em><\/strong> tal que:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/media.licdn.com\/dms\/image\/v2\/D4D12AQH1JbSqs-Dvow\/article-inline_image-shrink_400_744\/B4DZd53M8lGYAY-\/0\/1750096203948?e=1774483200&amp;v=beta&amp;t=muOxlKS_jpxq8vxNunWdfgmtABh4mO0KcA4waQt1bh8\" alt=\"Conte\u00fado do artigo\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/media.licdn.com\/dms\/image\/v2\/D4D12AQFhsXkObUb9KA\/article-inline_image-shrink_1000_1488\/B4DZd51kUSGkAY-\/0\/1750095775406?e=1774483200&amp;v=beta&amp;t=d1bBLTc_8R4PrkJCsrLOYPn69n8gdX5YUlvZ2e1AQ4g\" alt=\"Conte\u00fado do artigo\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>S\u00e3o fatores n\u00e3o triviais de <strong><em>N<\/em><\/strong>.<\/li>\n\n\n\n<li>Caso contr\u00e1rio, repete-se o processo.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember87\">Onde Est\u00e1 a Parte Qu\u00e2ntica?<\/h3>\n\n\n\n<p id=\"ember88\">O <strong>passo 2<\/strong> \u2014 encontrar o <strong>per\u00edodo <\/strong><strong><em>r<\/em><\/strong><strong> <\/strong>\u2014 \u00e9 onde o computador qu\u00e2ntico brilha. Esse problema \u00e9 classicamente exponencial, mas na computa\u00e7\u00e3o qu\u00e2ntica \u00e9 resolvido via:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Transformada de Fourier Qu\u00e2ntica (QFT)<\/strong><\/li>\n\n\n\n<li><strong>Superposi\u00e7\u00e3o de estados<\/strong><\/li>\n\n\n\n<li><strong>Colapso da fun\u00e7\u00e3o de onda ao medir o per\u00edodo<\/strong><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember90\">M\u00e3o na Massa \u2014 Testando Shor na Pr\u00e1tica<\/h3>\n\n\n\n<p id=\"ember91\">Embora computadores qu\u00e2nticos ainda n\u00e3o quebrem RSA-2048, \u00e9 poss\u00edvel experimentar na pr\u00e1tica usando simuladores qu\u00e2nticos.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember92\">Ferramentas Dispon\u00edveis<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/quantum-computing.ibm.com\/\">IBM Quantum Composer<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/qiskit.org\/\">Qiskit (Python SDK)<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/azure.microsoft.com\/pt-br\/products\/quantum\/\">Microsoft Azure Quantum<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/aws.amazon.com\/braket\/\">Amazon Braket<\/a><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember94\">Exemplo Pr\u00e1tico \u2014 Fatorar 15 com Qiskit<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>from qiskit import Aer, transpile, assemble, execute\nfrom qiskit.algorithms import Shor\nfrom qiskit.utils import QuantumInstance\n\n# Cria o algoritmo de Shor para fatorar o n\u00famero 15\nshor = Shor()\n\n# Configura backend (simulador qu\u00e2ntico)\nbackend = Aer.get_backend('aer_simulator')\n\n# Executa o algoritmo\nresult = shor.factor(N=15, quantum_instance=QuantumInstance(backend))\n\nprint(\"Fatores encontrados:\", result.factors) <\/code><\/pre>\n\n\n\n<p id=\"ember95\"><strong>Sa\u00edda esperada:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Fatores encontrados: &#91;&#91;3, 5]] <\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember96\">Fatora\u00e7\u00e3o de 21, 35 e 55 tamb\u00e9m \u00e9 poss\u00edvel em simuladores.<\/h3>\n\n\n\n<p id=\"ember97\"><strong>Se voc\u00ea modificar o valor de <\/strong>N<strong>:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Para N=21: Sa\u00edda t\u00edpica [[3, 7]]<\/li>\n\n\n\n<li>Para N=35: Sa\u00edda t\u00edpica [[5, 7]]<\/li>\n\n\n\n<li>Para N>100: Pode falhar ou exigir recursos computacionais intensivos no simulador.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember99\">Limita\u00e7\u00f5es Atuais<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Quebra de RSA real (2048 bits) requer:<\/li>\n\n\n\n<li>O maior feito at\u00e9 2024 foi fatorar <strong>RSA-48 bits<\/strong>, apenas experimental.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember101\">Atualiza\u00e7\u00f5es T\u00e9cnicas (2025)<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Pesquisadores da <strong>Tsinghua University<\/strong> publicaram um paper reduzindo a quantidade de qubits te\u00f3ricos necess\u00e1rios, usando algoritmos h\u00edbridos (qu\u00e2ntico + cl\u00e1ssico).<\/li>\n\n\n\n<li><strong>IBM<\/strong> anunciou o plano de entregar computadores qu\u00e2nticos com <strong>100.000 qubits f\u00edsicos at\u00e9 2029.<\/strong><\/li>\n\n\n\n<li>O <strong>NIST<\/strong> j\u00e1 finalizou a sele\u00e7\u00e3o de algoritmos resistentes \u00e0 computa\u00e7\u00e3o qu\u00e2ntica:<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember103\">Quer Testar Mais na Pr\u00e1tica?<\/h3>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember104\">Passos para rodar na sua m\u00e1quina (com simula\u00e7\u00e3o):<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Instale o Qiskit:<\/li>\n<\/ol>\n\n\n\n<pre class=\"wp-block-code\"><code>pip install qiskit <\/code><\/pre>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Crie seu notebook Python.<\/li>\n\n\n\n<li>Use o exemplo acima ou tente:<\/li>\n\n\n\n<li>Acompanhe a execu\u00e7\u00e3o do circuito qu\u00e2ntico.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember107\">Visualize o circuito:<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>circuit = shor.construct_circuit(N=15)\ncircuit.draw('mpl') <\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"ember108\">Conclus\u00e3o T\u00e9cnica<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>O <strong>Shor\u2019s Algorithm<\/strong> \u00e9 comprovadamente eficiente e pr\u00e1tico <strong>do ponto de vista matem\u00e1tico<\/strong>.<\/li>\n\n\n\n<li>A computa\u00e7\u00e3o qu\u00e2ntica ainda n\u00e3o est\u00e1 madura para quebrar RSA-2048 hoje, mas o caminho matem\u00e1tico e tecnol\u00f3gico j\u00e1 est\u00e1 tra\u00e7ado.<\/li>\n\n\n\n<li>A transi\u00e7\u00e3o para <strong>criptografia p\u00f3s-qu\u00e2ntica n\u00e3o \u00e9 opcional<\/strong>, \u00e9 obrigat\u00f3ria para qualquer empresa que queira manter seguran\u00e7a digital at\u00e9 2030.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>N\u00e3o costumo publicar aqui sobre computa\u00e7\u00e3o qu\u00e2ntica, mas faz parte do estudo! Ent\u00e3o bora l\u00e1! Shor\u2019s Algorithm na Pr\u00e1tica: Como Quebrar RSA na Era Qu\u00e2ntica O Algoritmo de Shor n\u00e3o \u00e9 mais apenas teoria \u2014 \u00e9 uma amea\u00e7a matem\u00e1tica real para qualquer algoritmo baseado na dificuldade de fatora\u00e7\u00e3o de inteiros ou logaritmos discretos, como RSA,<\/p>\n","protected":false},"author":1,"featured_media":471,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-470","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-quantum"],"_links":{"self":[{"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/posts\/470","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/comments?post=470"}],"version-history":[{"count":1,"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/posts\/470\/revisions"}],"predecessor-version":[{"id":472,"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/posts\/470\/revisions\/472"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/media\/471"}],"wp:attachment":[{"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/media?parent=470"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/categories?post=470"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/luizlohn.com.br\/blog\/wp-json\/wp\/v2\/tags?post=470"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}