Fatoração de Números Inteiros (Shor)

Conteúdo

O Algoritmo de Shor é um dos marcos fundamentais da computação quântica, servindo como demonstração prática mais impactante da supremacia quântica sobre paradigmas clássicos. O algoritmo é a ponte que conecta princípios profundos da teoria de números com o poder exponencial do paralelismo quântico, permitindo-nos “desvendar” a estrutura multiplicativa de inteiros - um problema que há séculos resiste aos ataques dos mais avançados algoritmos clássicos. Mais do que uma ferramenta de fatoração, Shor é a materialização quântica que transforma o problema aparentemente intratável da periodização modular em informação mensurável, expondo assim as fundações teóricas que sustentam sistemas criptográficos globais e redefinindo os limites do computável.

Fatoração de Números Inteiros (Shor)#

AVISO: Para o entedimento completo do algorítmo de Shor é necessário conhecimento perante o Algorítmo de Estimação de Fase Quântica e Transformada Quântica de Fourier

O Problema da Fatoração de Números Inteiros#

O Problema da Fatoração de Números Inteiros constitui um dos desafios computacionais mais fundamentais e persistentes da matemática e ciência da computação. Em sua essência, o problema questiona: dado um número composto N, como encontrar eficientemente seus fatores primos? Enquanto verificar se um número é primo é relativamente fácil, fazer o caminho inverso, descobrir quais números primos multiplicados geram um número grande, é extremamente complexo e consome muito tempo.

\[ N = p \times q \]

onde $p$ e $q$ são números primos.

Organização do Algorimto de Shor#

Para compreender o algoritmo desenvolvido por Peter Shor, é fundamental reconhecer que sua estrutura lógica envolve etapas de pré-processamento e pós-processamento, ambas realizadas de forma clássica.

Algoritmo de Shor#

Para uma melhor visualização, apresentaremos o Algoritmo de Shor utilizando o seguinte exemplo:

\[ N = 15 \]

Pré-processamento Clássico#

Como pré-processamento, devemos escolher um número $a$ tal que $\mathrm{mdc}(a, N) = 1$. Para este exemplo, escolheremos $a = 7$.

Processamento Quântico#

Utilizaremos o Circuito de Shor (explicado futuramente), que implementa a Série de Euler (também explicada futuramente), para estimar o valor de $r$, tal que $a^r \equiv 1 \pmod{15}$.

Para o exemplo, precisamos encontrar um valor de $r$ tal que

\[ 7^r \equiv 1 \pmod{15}. \]

Aplicando o Circuito de Shor ou realizando a Série de Euler de maneira clássica, encontramos $r = 4$.

Pós-processamento Clássico#

Agora devemos calcular os seguintes mdc:

\[ \mathrm{mdc}\left(a^{r/2} - 1,, N\right) \]

\[ e \]

\[ \mathrm{mdc}\left(a^{r/2} + 1,, N\right), \]

para descobrirmos os fatores primos $p$ e $q$ cujo produto resulta em $N$.

Seguindo o nosso exemplo, temos:

\[ p = \mathrm{mdc}\left(7^{4/2} - 1,, 15\right) = \mathrm{mdc}\left(48,, 15\right) = 3 \]

\[ e \]

\[ q = \mathrm{mdc}\left(7^{4/2} + 1,, 15\right) = \mathrm{mdc}\left(50,, 15\right) = 5. \]

Resultado#

Portanto, utilizando o Algoritmo de Shor, identificamos que o número 15 é o resultado da multiplicação dos números 3 e 5.

Série de Euler#

Uma vez compreendidos os principais passos do Algoritmo de Shor, torna-se necessário entender a matemática que envolve o processamento quântico. Para compreender essa etapa com clareza, é fundamental ter conhecimento da Série de Euler.

Como visto anteriormente, calcular ${17 \times 3}$ é simples. Porém, dado o número $51$, é mais difícil encontrar seus fatores primos. Para números menores, mesmo que de forma demorada, esses problemas são solucionáveis. Entretanto, ao tratar de protocolos, como os de criptografia, são utilizados números com centenas de dígitos, aumentando significativamente a dificuldade da fatoração.

Tendo em vista o problema da fatoração, o matemático Leonhard Euler desenvolveu importantes contribuições que posteriormente se tornaram fundamentais para o entendimento teórico por trás dos algoritmos de fatoração.

Euler descobre um padrão ao observar uma série $m$ de potências de 2:

\[ m = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, \ldots \]

Aplicando $\mod 5$ em cada item dessa série, obtemos o seguinte resultado:

\[ m \mod 5 = 1, 2, 4, 3, 1, 2, 4, 3, 1, 2, 4, 3 \]

Nota-se que, nessa série, os valores $[1, 2, 4, 3]$ se repetem indefinidamente, com período 4.

Se aplicarmos $\mod 15$ na mesma série $m$ original, notamos que obteremos o seguinte padrão:

\[ m \mod 15 = 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8 \]

Dessa vez, os valores obtidos são diferentes quando comparados a $m \mod 5$: $[1, 2, 4, 8]$ se repetem indefinidamente, porém com o mesmo período exato, 4.

Com isso, Euler percebeu que, dada a sequência $[x \mod N, x^2 \mod N, x^3 \mod N, x^4 \mod N, \ldots]$, se $N$ é o produto de dois primos $p$ e $q$, e $x$ não é divisível por $p$ nem por $q$, a sequência se repete com um período que divide $(p - 1)(q - 1)$.

Circuito de Shor#

O Algoritmo de Shor possui uma estrutura muito similar ao Algorítmo de Estimação de Fase (QPE), pois, assim como o QPE, o Algorítmo de Shor é uma aplicação fundamental da Transformada Quântica de Fourier (QFT) que permite estimar o autovalor de um operador unitário.

Dado um número composto N que desejamos fatorar, e um inteiro a coprimo com N, encontre o menor inteiro positivo r tal que:

\[a^r \equiv 1 \pmod{N}\]

Portanto, necessita-se dos seguintes recursos quânticos:

Registro de controle: $t$ qubits para estimação de fase ($t \approx 2\log_2 N$)
Registro de trabalho: $n$ qubits para representar números módulo N ($n = \lceil \log_2 N \rceil$)
Operador unitário: $U_a$ definido por $U_a\ket{x} = \ket{ax \mod N}$

Circuito Quântico de Shor#

O Algoritmo de Shor é implementado através de um circuito composto por portas Hadamard e operadores unitários. O procedimento para $m$ qubits em ${\ket{0}}$ e $n$ qubits é:

Procedimento:

\[\begin{split} \begin{array}{ccc} \text{Etapa 0:} & \ket{0}^{\otimes m} \ket{v} & \text{Inicializa m qubits em 0 e n qubits em v} \\ \text{Etapa 1:} & H\ket{\psi_0} & \text{Coloca os qubits incializados em 0 em superposição} \\ \text{Etapa 2:} & U^1\ket{\psi_1} & \text{Aplica o operador unitário no primeiro qubit v} \\ \vdots & \vdots & \vdots \\ \text{Etapa m:} & U^{2^{m-1}}\ket{\psi_{m-1}} & \text{Aplica o operador unitário no n-ésimo qubit em v} \\ \text{Etapa m+1:} & \text{IQFT} \ket{\psi_m} & \text{Aplica a IQFT nos m qubits} \\ \end{array} \end{split}\]

Circuito

Notação expandida:

Análise detalhada do algoritmo:

Estado Inicial: $$\ket{\psi_0} = \ket{0}^{\otimes t} \otimes \ket{1}^{\otimes n}$$

Aplicamos Hadamard nos qubits inicializados em $\ket{0}$:

\[H^{\otimes t}\ket{\psi_0} = \frac{1}{\sqrt{2^t}} \sum_{j=0}^{2^t-1} \ket{j} \otimes \ket{1}\]

Aplicação Controlada do Operador Modular:

Para cada qubit $k$ no registro de controle ($k = 0, 1, \dots, t-1$), aplicamos $U_a^{2^k}$ controlado:

\[\ket{\psi_2} = \frac{1}{\sqrt{2^t}} \sum_{j=0}^{2^t-1} \ket{j} \otimes U_a^j\ket{1} = \frac{1}{\sqrt{2^t}} \sum_{j=0}^{2^t-1} \ket{j} \otimes \ket{a^j \mod N}\]

Aplicação da Transformada Quântica de Fourier Inversa (IQFT)

Aplicamos QFT$^\dagger$ no registro de controle:

\[\ket{\psi_3} = \text{QFT}^\dagger \otimes I \ket{\psi_2}\]

Medição Medimos o registro de controle para obter uma aproximação da fase.

Complexidade

A complexidade do algoritmo é ${O(t^2 + t \cdot C_U)}$, em que $C_U$ é custo de implementar $U$

Simulação do algorítimo de Shor#

Para simular o algorítimo de Shor usaremos a línguagem Ket de computação quântica, para isso precisamos ter ela instalada, caso não possua o pacote instalado rode o seguinte código:

pip install ket-lang

Com a biblioteca instalada, importa-se para ser usada dentro do seu código:

from ket import *
from math import pi, log2, gcd, sqrt
from random import randint
from fractions import Fraction

O Algorítmo de Shor utiliza a $IQFT$, portanto, é necessário a implementação da Transformada Quântica de Fourier (QFT), que já foi explicada anteriormente.

def qft(qubits, do_swap: bool = True):
    if len(qubits) == 1:
        H(qubits)
    else:
        *init, last = qubits
        H(last)

        for i, ctrl_qubit in enumerate(reversed(init)):
            with control(ctrl_qubit):
                P(pi / 2 ** (i + 1), last)

        qft(init, do_swap=False)

    if do_swap:
        size = len(qubits)
        for i in range(size // 2):
            SWAP(qubits[i], qubits[size - i - 1])

Uma vez que a implementação da Transformada Quântica de Fourier foi feita, pode-se implementar o Algorítmo de Shor

def qu_exp(a: int, x: Quant, n: int, y: Quant):
    for state in range(2 ** len(x)):
        with control(x, state):
            qulib.math.set_int(y, pow(a, state, n))


def shor_quantico(a: int, N: int):
    processo = Process()

    n = N.bit_length()
    x = processo.alloc(n)
    y = processo.alloc(n)

    H(x)
    qu_exp(a, x, N, y)
    measure(y)
    adj(qft)(reversed(x))
    resultado = max(
        Fraction(r / 2**n).denominator for r in sample(x).get().keys() if r != 0
    )

    return resultado

def shor(N):
    # Se N for par, retorna o fator 2.
    if N % 2 == 0:
        return 2

    # Se N = a^b para inteiros a >= 1 e b >= 2, retorna a.
    n = N.bit_length()
    y = int(log2(N))
    for b in range(2, n + 1):
        x = y / b
        u1 = int(2**x)
        u2 = u1 + 1

        if u1**b == N:
            return u1
        elif u2**b == N:
            return u2

    # Escolhe a aleatoriamente. Se mdc(a, N) > 1 retorna mdc(a, N).
    for _ in range(n):
        a = randint(2, N - 1)
        mdc_a_N = gcd(a, N)
        if mdc_a_N > 1:
            print("sorte!")
            return mdc_a_N

        # Encontrando a ordem com algoritmo quântico
        r = shor_quantico(a, N)

        if r % 2 == 0 and pow(a, r // 2, N) != N - 1:
            p = gcd(a ** (r // 2) - 1, N)
            if p != 1 and p * N // p == N:
                return p

            q = gcd(a ** (r // 2) + 1, N)
            if q != 1 and q * N // q == N:
                return q

    raise RuntimeError("Falha ao fatorar, tente novamente")

N = 187
a = shor(N)
print(f"{a} x {N//a} = {N}")

17 x 11 = 187

Ket	v0.9.2.8
Libket	v0.6.0
KBW	v0.4.2