Como funciona o Algoritmo de Shor?

• Introdução
• Um resumo sobre a Criptografia RSA
  • Brincando de fatorar
  • O Coração da RSA
• O Algoritmo de shor
  • A Aritmética Modular
  • Numeros giratórios
  • A “Equação de Shor”
  • Módulo de Potências
  • Juntando os pedaços
• A Mecânica Quântica
  • QuBits
  • Portões Lógicos Quânticos
  • Um Exemplo
  • Aplicando ao Algoritmo de Shor
  • Mais padrões ciclicos em p
  • Transformada Quântica de Fourier
• Conclusão
• Saiba Mais
  • Referências
  • Aprofundamento
  • Apêndice
    • Teorema da Raiz
    • Diferença de quadrados
    • Demonstração da Ciclicidade em p

Introdução

“É um resultado verdadeiramente impressionante. Este é o primeiro problema realmente útil que se demonstrou ser solucionável em um computador quântico.”

Peter Shor, 2014

Talvez você já tenha ouvido falar de um dos mais famosos algoritmos criados para computadores quânticos.

A promessa do Algoritmo de Shor é fornecer um jeito fácil de quebrar a Criptografia RSA, que é uma das encriptações assimétricas mais usadas atualmente.

Mesmo que não saiba, você usou RSA pra acessar esse site e também usa toda vez que loga em algum serviço ou aplicativo.

A Criptografia RSA é fundamental para verificar a identidade e garantir privacidade na troca de dados entre computadores.

Abaixo deixo um breve resumo sobre como funciona a Criptografia RSA.

Sinta-se a vontade para usar o sumário para pular para os trechos que mais te interessam!

Um resumo sobre a Criptografia RSA

Nomeada em honra aos seus criadores (Rivest, Shamir e Adleman), a RSA foi desenvolvida em 1977 para resolver problemas de privacidade e segurança.

A efetividade da RSA está na dificuldade de fatorar números grandes.

Ainda não existe uma forma rápida de fazer isso.

Brincando de fatorar

Suponha que você quer encontrar os fatores do número 28. Em outras palavras, você quer saber quais números multiplicados resultam em 28.

Você pode perceber de cara que tem algumas opções: 2*14, 4*7 2*2*5.

Agora perceba uma coisa, podemos reduzir as duas primeiras fatorações à terceira, mas a terceira não pode ser reduzida.

O que estou dizendo é: 14 é 2*7 e 4 é 2*2, mas não tem como fatorar o próprio 2 ou o próprio 7 em algo menor.

Por terem essa propriedade atômica ou primordial, esses números são chamados de Números Primos.

Ok… calças espertas, mas onde está a dificuldade nisso?

Bom, com números pequenos é fácil fazer, 56 é 2*2*2*7 e 121 é 11*11, mas tente fazer com 598598!

Os espertinhos de plantão vêem logo que esse número é divisivel por 2 e ficam com 299299.

Outro mais dedicado vai continuar tentando outros primos e chega a conclusão que também é divisivel por 13, obtendo 23023.

E assim você vai indo, testando um primo por vez até encontrar todos os fatores: 2*7*11*13*13*23.

Percebe-se rapidamente que quanto maior forem os primos que compõe esse número, mais tempo você vai ficar testando sua lista de primos nele.

Na criptografia RSA moderna, o tamanho padrão recomendado é um número de 2048 bits, algo como:

$$30325492167732230485987625121898711462002319223847352345032569426 \\ 72186717548742548237618843232145612300584725321087452361254395874 \\ 32104587623105487621305487213654872163458761238475612384726354182 \\ 73645812736458127364581273645812734658127364581273645812736458127 \\ 34658127364581273645812736458127364581273645812736458127364581273 \\ 64581273645812736458127364581273645812736458127364581273645812736 \\ 45812736458127364581273645812736458127364581273645812736458127364 \\ 58127364581273645812736458127364581273645812736458127364581273645 \\ 81273645812736458127364581273645812736458127364581273645812736458 \\ 12736458127364581273645812736458127364581273645812736458127364519$$

Fatorar esse safadinho levaria alguns bilhões de anos. Mesmo se você tentar só até a raiz quadrada dele.

O Coração da RSA

Escolhemos dois números primos grandes e os múltiplicamos pra ter um número composto maior ainda.

Aqui está o segredo:

• Guarde pra você um desses fatores primos, ele é sua Chave Privada.

• Use o número composto gigante como Chave pública.

A lógica por trás de transformar esses números em chaves que encriptam e desencriptam informação é um outro assunto.

O importante aqui é entender que o coração desse método está na dificuldade de fatorar a chave pública para encontrar a privada.

O Algoritmo de shor

Nosso objetivo principal é fatorar um número gigante composto por dois primos.

O Algoritmo de Shor é um pouco complicado e usa bastante matemática modular.

Vamos encarar ele por partes.

Sinceramente, nenhuma das partes faz muito sentido sozinha, mas espero que quando chegar ao fim, você entenda como elas se integram.

A Aritmética Modular

Todo esse papo de dividir e multiplicar pode ser rastreado à Aritmética modular.

O conceito principal é o seguinte: vamos olhar para como um número se relaciona com os múltiplos de um outro número.

Talvez você lembre de uma definição da operação de divisão, lá de quando você era um pingo de gente:

$a = q*b + r$

Aqui estamos representando a divisão de a por b.

Chamamos q de quociente e r de resto.

Exemplo $15 \div 6$

$15 = 2*6 + 3$

Na matemática modular, simplesmente passamos a chamar esse resto r de a mod b.

Veja mais alguns exemplos:

15 mod 6 = 3; porque 15 = 2*6 + 3

2 mod 10 = 2; porque 2 = 0*10 + 2

52 mod 49 = 3; porque 52 = 1*49 + 3

Eu sei, você deve estar se perguntando: pra que diabos alguém faria isso?

Bom, pro nosso caso aqui, é pra encontrar frequências.

Vamos um pouco além.

Numeros giratórios

Uma propriedade importante da operação mod, é que ela é cíclica.

Quando calculamos o mod de um número é como se colapsassemos a reta dos numeros naturais:

em um círculo:

Dessa forma, as posicões se repetem.

Pense num relógio. A posição do ponteiro funciona como uma operação de mod 12.

Ou seja, a cada 12 posições, tudo começa de novo.

A “Equação de Shor”

Não leve esse nome a sério, provavelmente eu sou o único que chama ela assim.

Antes de tudo, aqui está a ideia central do Algoritmo, nas minhas palavras:

Dado um chute c, existe a possibilidade de encontrar fatores de um numero N proporcionais a:

$(c^{p/2} - 1)*(c^{p/2} + 1)$

UAU! Ver isso pela primeira vez é bem esclarecedor.

Esqueça a forma da equação por um segundo e foque na ideia por trás dela:

• Pego um número aleatório c.
• Esse número c vai me levar a um número p específico.
• Com esses dois números, posso calcular os números $(c^{p/2} - 1)$ e $(c^{p/2} + 1)$.
• Existe a chance de esses números serem fatores de N ou proporcionais a fatores de N.

Hmm …

Existe uma chance? Então o Algoritmo de Shor é probabilístico!

Nem todo chute que você escolher vai te levar aos seus tão desejados primos.

Pela equação, vemos que existem pelo menos duas restrições:

1. p precisa ser par
   Como estamos lidando com números naturais, nada de tirar raízes.

2. $(c^{p/2} - 1)$ ou $(c^{p/2} + 1)$ não podem ser iguais a N
   Se um deles for igual N, então o outro será um múltiplo qualquer e não conseguimos fatorar nada.

Para o caso da RSA, dado um chute c, há uma chance de no mínimo 50% de encontrar fatores.

E quanto mais tentativas, essa probabilidade aumenta exponencialmente. De forma que após 10 tentativas a chance é maior que 99,9%.

E de onde Shor tirou essa equação?

EU não me apegaria muito a como ele chegou a equação.

Não é pra ser intuitivo pra alguém que não está ativamente procurando quebrar a RSA.

Esse cara se alimenta de matemática no café da manhã, almoço e jantar.

Portanto, não se sinta mal. Vamos focar em entender o resultado.

Módulo de Potências

Quer saber? E se pegarmos números pequenos e calcularmos algumas potências?

Se o problema geral é muito complexo, pode ser muito útil olhar para ele num caso específico e simples.

Vejamos os valores de $2^x mod 15$:

$$2^0 mod 15 = 1 \\ 2^1 mod 15 = 2 \\ 2^2 mod 15 = 4 \\ 2^3 mod 15 = 8 \\ 2^4 mod 15 = 1 \\ 2^5 mod 15 = 2 \\ 2^6 mod 15 = 4 \\ 2^7 mod 15 = 8 \\ ...$$

Olha só! Esses valores se repetem: [1,2,4,8,1,2,4,8,...]

Lembra daquele papo de que mod é uma operação cíclica? Apareceu de novo.

Ora, como todo numero elevado a 0 é igual a 1, faz sentido dizer que nesses ciclos sempre teremos um resto r=1.

Por que? Simples: o primeiro valor sempre será igual a 1, e o mod é cíclico, então haverão outros 1.

🚨🐈⬆️ Jump of the cat!!!

Sempre existem expoentes p, que nos trazem de volta ao resto 1

Colocando isso numa equação:

$c^p mod N = 1$

Ou seja, podemos escrever que:

$c^p = m*N + 1$

Agora, com um pouco de matemágica:

$$c^p - 1 = m*N \\ (c^{p/2} - 1)*(c^{p/2} + 1) = m*N$$

Que é a “Equação de Shor”!

Um número vezes outro número é proporcional ao número que queremos fatorar

Juntando os pedaços

Vimos que a “Equação de Shor” nasce da observação que módulos de potências tem ciclos que passam pelo número 1.

Mais ainda, o expoente p que encontramos no chute é essa frequência de repetição.

Nesse exemplo que eu dei, da pra ver que p=4, porque os valores se repetam a cada 4 cálculos, e ao mesmo tempo:

$$2^4 mod 15 = 1 \\$$

Você pode notar que existem vários valores de p, porque é um ciclo que se repete.

Não precisamos de todos, encontrar o primeiro p diferente de zero é suficiente.

Outra coisa que podemos perceber é que quanto maior o número N, mas vai demorar para o periodo p aparecer.

Vamos tentar “aplicar” o Algoritmo de Shor pra um caso simples, onde não precisamos de um computador quântico:

Exemplo: N=15, g=7

Por tentativa e erro, encontramos a potência p=4

$$7^4 = 160 * 15 + 1 \\$$

Os números de shor são:

$$7^{4/2} - 1 = 48 \\ 7^{4/2} + 1 = 50$$

Que não são fatores diretos de 15, pois 48*50 é bem maior que 15

Mas se decompormos:

$$48=3*16 \\ 50=5*10$$

Ai estão os fatores de 15: 3 e 5.

Claro que, para números grandes, você usaria o Algoritmo de Euclides para encontrar os máximos divisores comuns. Mas não se preocupe, ele já é bem eficiente em computadores clássicos.

UFA!

Olha se você chegou aqui, já pode se sentir bem descolado

Esse é o Algoritmo de Shor, a partir de agora vamos entrar em como a Mecânica Quântica consegue nos ajudar a fazer esse cálculo de forma rápida.

A Mecânica Quântica

“O mundo da mecânica quântica não é o mundo da sua intuição. A mecânica quântica é a maneira como o mundo realmente é.”

Peter Shor, 2023

Num computador clássico, precisaríamos calcular exponenciais para encontrar p por tentativa e erro.

Usando um computador quântico, vamos preparar uma superposição de inteiros, e fazê-los passar por operações que vão exponenciar os números e depois fazer os estados inteferirem entre si de forma destrutiva, de forma que o valor final medido nos leve diretamente ao valor de p correto.

E o que é uma superposição?

Num primeiro momento, você pode pensar numa superposição quântica como uma combinação de probabilidades.

Um sistema quântico tem certas propriedades que são probabilísticas, ou seja, não existe uma forma de prever com certeza qual será seu valor.

Como exemplo, imagine que você colocasse uma partícula quântica dentro de uma caixa.

Por sua natureza, a posição dessa partícula ao longo do tempo será probabilistica, ou seja, não há como prever com exatidão onde a partícula estará.

Se você medisse a posição da partícula de tempos em tempos, vai descobrir que ela tem mais chance de estar perto do centro, e menos de estar nas bordas. Um possível gráfico que mostra a probabilidade de achar a partícula numa dada posição da caixa é:

No caso dos computadores quânticos, um sistema pode ter uma probabilidade de ser 0 e uma probabilidade de ser 1. Dizemos então que existe uma Superposição dos estados 0 e 1.

TLDR: Um computador quântico recebe um sistema físico em superposição e manipula as probabilidades dos estados, de forma que ao medir o sistema o valor seja na maioria das vezes o valor desejado pelo algoritmo utilizado.

Essa é a visão geral, vamos analisar mais de perto… 🔎

QuBits

Um QuBit pode assumir os estados $\vert 0 \rangle$ e $\vert 1 \rangle$ (*).

De modo geral, um sistema quântico estará numa superposição desses estados.

Isso equivale a dizer que se você for medir o sistema, terá alguma probabilidade de obter o valor 1 e outra de obter o valor 0.

Essa probabilidade depende diretamente das propriedades físicas do sistema.

Sempre que você medir o sistema, o qubit colapsará em um único valor, e deverá ser preparado novamente.

(*) Esta notação $\vert x \rangle$ representa um estado quântico.

Portões Lógicos Quânticos

Para operar em estados quânticos e criar funções, precisamos montar Portões Lógicos.

Talvez você se lembre de portões lógicos clássicos.

Eles são circuitos eletrônicos que recebem sinais (correntes elétricas) e retornam algum resultado.

Por exemplo, o portão AND executa a mesma função do operador lógico AND:

Ou seja, se recebermos $0$ e $1$, retornamos $0$.

Funciona da mesma forma que $true$ AND $false$ retorna $true$.

Os Portões Quânticos seguem uma ideia parecida, mas ao invés de receberem valores definidos e retornarem valores definidos, eles geralmente recebem superposições quânticas e podem alterar as probabilidades de cada estado, mas ainda retornando outra superposição quântica.

Alguns exemplos de Portões Quânticos são:

• Portão de Hadamard: Transforma um qubit medido em uma superposição, com 50% de chance de medir o estado $\vert 0 \rangle$ e 50% de medir o estado $\vert 1 \rangle$.
• Porta Pauli-X (NOT): Troca as probabilidades, ou seja a probabildiade de $\vert 0 \rangle$ vira a de $\vert 1 \rangle$ e vice-versa.

Não vamos entrar em como fisicamente isso é feito, mas basta entender que podemos criar funções que atuam numa superposição quântica para manipular seus estados.

Mais ainda, a capacidade de operar em uma superposição de estados é o que define sua superioridade em relação a um computador clássico no algoritmo de Shor.

Essa capacidade é chamada de paralelismo quântico.

Um Exemplo

Vamos a um exemplo para clarear os conceitos.

Suponha que queremos executar a busca de um item, numa lista de, digamos, 256 itens.

Num computador clássico, podemos representar cada item com uma sequencia de 8 bits, ou 1 byte:

0000 0000, 0000 0001, 0000 0010, 0000 0011, … , 1111 1110, 1111 1111.

Da mesma forma, em um computador quântico, precisariamos de 8 qubits. Cada um correspondendo a um item da lista.

Suponha que temos uma função de checagem f(x), ela simplesmente recebe um desses bytes x e retorna se é o item que buscamos, ou não.

No nosso computador clássico executamos essa função pra cada byte, até encontrar esse item. No pior dos casos, teremos que tentar 256 vezes.

🚨🐈⬆️ Jump of the cat!!!

Um qubyte em superposição possui probabilidade de ser qualquer um dos itens da lista.

Se essa função de checagem for alterada para usar portões lógicos quânticos, podemos realizar manipulações nas probabilidades, de forma que quando medirmos o qubit, ele tenha uma probabilidade alta de ser o número que procuramos!

Esse é o paralelismo quântico em ação, ao invés de 256 testes, precisariamos de cerca de 16 testes! Isso porque as interferências entre os estados quânticos aumentam drasticamente a probabilidade de obter a busca correta!

Essa ideia que acabo de descrever é central para o Algoritmo de Groove, recomendo fortemente o vídeo do 3Blue1Brown sobre o tópico.

Aplicando ao Algoritmo de Shor

A idea é:

• Preparar uma superposição quântica com diversos inteiros $x$.
• Jogar essa superposição numa função que calcula $c^x$, onde $c$ é o nosso chute.
• Encaminhar a superposição para outra função que calcula a diferença entre $c^x$ e um múltiplo de $N$

Se fizermos isso, teremos então uma superposição de estados $\vert x, r \rangle$, por exemplo:

$..., \vert 432, 3579 \rangle , \vert 432, 12 \rangle, \vert 432, 1 \rangle, \vert 8324, 12 \rangle, ...$

Cada um com uma certa probabilidade de aparecer se medirmos o sistema.

Lembre-se, o que precisamos para quebrar a RSA é uma potência $x$ que possui resto $r = 1$.

Ou usando a terminologia da parte anterior, queremos o valor $x = p$.

Para conseguir avançar, vamos precisar de uma última observação matemática sobre a aritmética modular.

Mais padrões ciclicos em p

Se temos um $x$ tal que:

$$g^x = m_1*N + r$$

Então podemos afirmar que:

$$g^{(x+p)} = m_2*N + r$$

Ou seja, adicionar $p$ que satisfaz $g^p=m*N+1$, não altera o resto.

Eu sei, você quer uma prova disso. Só olhar aqui

O mesmo vale para adicionar $2p$, remover $p$, ou qualquer multiplo de $p$.

🚨🐈⬆️ Jump of the cat!!!

Se medirmos um dado resto r na superposição, ficaremos com uma superposição de todos os valores possíveis de $x$ que tem resto $r$

AHÁ! Nós sabemos que, se p existe, a distância entre essas potências x é sempre igual a p!

Em outras palavras, os valores de x dentro da superposição se repetem com frequência 1/p.

Isso me faz pensar, seria tão bom se existisse uma ferramenta matemática para medir frequências numa superposição quântica…

PERA AI! Isso é a

Transformada Quântica de Fourier

Explicar a Transformada Quântica de Fourier levaria um post inteiro, no mínimo.

Resumidamente, a TQF faz exatamente o que precisamos, dado um estado quântico, podemos decompor a função de onda em suas frequências primordiais.

Espera ai, eu não expliquei o que é uma função de onda, né? Bom, é simples.

Um sistema quântico pode ser representado por uma onda. Essa onda está ligada a probabilidade de um sistema apresentar um certo estado.

Esse post já está bem gigantesco, então por favor consulte o aprofundamento para mais detalhes.

Se aplicarmos a TQF a função de onda, que é a representação matemática da nossa superposição de estados, conseguimos descobrir a frequência:

Em uma superposição de inteiros separados por p, recebemos exatamente 1/p:

$$QFT[\vert 432, r \rangle, \vert 123, r \rangle, \vert 67, r \rangle ... ] -> 1/p$$

Finalmente! CONSEGUIMOS p!!!

Conclusão

OK, percorremos um longo caminho. Mas finalmente chegamos, aqui está o resumo:

• Podemos encontrar ótimos chutes para os fatores de um dado número N usando a “Equação de Shor”.

• Chutamos um número c, encontramos um p que satisfaz $c^p mod N = 1$ usando um computador quântico e aplicando a Transformada Quântica de Fourier.

• Se p é par, então podemos calcular os valores $(c^{p/2} - 1)$ e $(c^{p/2} + 1)$

• Se esses valores não são diretamente múltiplos de N, então usamos o Algoritmo de Euclides para encontrar os fatores.

Se isso não der certo, chutamos outro c, e tentamos de novo.

Com poucas tentativas, devemos ser capazes de encontrar os fatores primos do número N.

É isso!

Esse é o Algoritmo de Shor.

Claro, essa é uma versão extremamente simplificada e eu não sou um pesquisador na área, então prefira dar ouvidos às referências abaixo.

Até o próximo!

---

Saiba Mais

Referências

Sobre a probabilidade do Algortimo de Shor retornar fatores úteis

Video do MinutePhysics

Video do Computerphile

Partícula Quântica em uma Caixa

Shor sobre a descoberto do Algoritmo

Shor sobre a Mecânica Quântica

Aprofundamento

O Artigo original do Sr Shor:

Shor, P. W. (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing, 26(5), 1484–1509.

Sobre Ondas e a Transformada Quantica de Fourier - Numberphile

Quantum Instructions set - Numberphile

O Algoritmo de Groove - 3Blue1Brown

Post do Phill

Curso Gratuito da IBM

Apêndice

Teorema da Raiz

Se um número $N$ é composto, ele obrigatoriamente deve possuir pelo menos um fator primo menor ou igual à sua própria raiz quadrada ($\sqrt{N}$).

Se ambos os fatores fossem maiores que $\sqrt{N}$, então o produto deles $p*q$ seria maior que $N$:

$\sqrt{N} * \sqrt{N} = N$,

O que é uma contradição. Portanto, para garantir que vamos encontrar o menor fator primo por força bruta, só precisamos testar os números inteiros até $\sqrt{N}$.

Diferença de quadrados

Sempre que você tiver um número menos outro número, você pode fatorá-los num produto.

Isso é tradicionalmente feito quando temos dois quadrados, por exemplo:

$a^2 - b^2 = (a+b)*(a-b)$

Você pode distribuir a multiplicação e ver que de fato só sobram os fatores $a^2$ e $b^2$.

Claro, no caso do algoritmo de shor, não tinha nada ao quadrado, mas a equação continua válida se trocarmos a e b por $\sqrt{a}$ e $\sqrt{b}$

$$(\sqrt{a})^2 - (\sqrt{b})^2 = (\sqrt{a} + \sqrt{b})*(\sqrt{a} - \sqrt{b}) \\ a - b = (\sqrt{a} + \sqrt{b})*(\sqrt{a} - \sqrt{b})$$

Demonstração da Ciclicidade em p

Comece com:

$$g^x = m_1*N + r$$

Agora, adicione $p$ ao expoente de $p$, você pode fazer isso multiplicando por $g^p$:

$$g^x * g^p = (m_1*N + r)*g^p \\ g^{x+p} = (m_1*N + r)*g^p$$

Agora lembre-se que $p$ possui uma propriedade especial: $g^p = m*N + 1$:

$$g^{x+p} = (m_1*N + r)*(m*N + 1) \\ g^{x+p} = m_1*N*m*N + r*m*N + m_1*N + r \\$$

Organizando os termos temos:

$$g^{x+p} = (m_1*N*m + r*m + m_1)*N + r$$

Que nada mais é do que um numero inteiro $m_2$, ou seja:

$$g^{x+p} = m_2*N + r$$

Como queríamos demonstrar.