Dois exemplos: fatoração e MDC

Os computadores clássicos que existem hoje são incrivelmente rápidos, e sua velocidade parece estar sempre aumentando. Por isso, alguns podem ser levados a acreditar que os computadores são tão rápidos que nenhum problema computacional está fora do seu alcance.

Essa crença é falsa. Alguns problemas computacionais são tão intrinsecamente complexos que, embora existam algoritmos para resolvê-los, nenhum computador no planeta Terra hoje é rápido o suficiente para executar esses algoritmos até a conclusão, mesmo para entradas de tamanho moderado, dentro do tempo de vida de um ser humano — ou até mesmo dentro do tempo de vida da própria Terra.

Para explicar melhor, vamos apresentar o problema da fatoração de inteiros.

Fatoração de inteiros

Entrada: um inteiro $N\geq 2$
Saída: a fatoração em primos de $N$

Por fatoração em primos de $N$ entendemos uma lista dos fatores primos de $N$ e as potências às quais eles devem ser elevados para obter $N$ por multiplicação. Por exemplo, os fatores primos de $12$ são $2$ e $3,$ e para obter $12$ devemos tomar o produto de $2$ elevado à potência $2$ e $3$ elevado à potência $1.$

$$12 = 2^2 \cdot 3$$

Salvo a ordem dos fatores primos, existe apenas uma fatoração em primos para cada inteiro positivo $N\geq 2,$ fato esse conhecido como o teorema fundamental da aritmética.

Algumas demonstrações simples de código em Python serão úteis para explicar melhor a fatoração de inteiros e outros conceitos relacionados a esta discussão. As importações a seguir são necessárias para essas demonstrações.

# Added by doQumentation — required packages for this notebook
!pip install -q sympy

import math
from sympy.ntheory import factorint

A função factorint do pacote de matemática simbólica SymPy para Python resolve o problema da fatoração de inteiros para qualquer entrada $N$ que escolhermos. Por exemplo, podemos obter a fatoração em primos de 12, que naturalmente concorda com a fatoração acima.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Fatorar números pequenos como $12$ é fácil, mas quando o número $N$ a ser fatorado fica maior, o problema se torna mais difícil. Por exemplo, executar factorint em um número consideravelmente maior causa um atraso curto, mas perceptível, em um computador pessoal típico.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

Para valores ainda maiores de $N,$ as coisas se tornam impossíveis, pelo menos até onde sabemos. Por exemplo, o Desafio de Fatoração RSA, conduzido pela RSA Laboratories de 1991 a 2007, oferecia um prêmio em dinheiro de $100.000 para fatorar o número a seguir, que possui 309 dígitos decimais (ou 1024 bits quando escrito em binário). O prêmio para esse número nunca foi reivindicado e seus fatores primos permanecem desconhecidos.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Não vale a pena tentar executar factorint no RSA1024 — ele não terminaria durante nossas vidas.

O algoritmo mais rápido conhecido para fatorar inteiros grandes é conhecido como a peneira do corpo numérico. Como exemplo do uso desse algoritmo, o número do desafio RSA250, que possui 250 dígitos decimais (ou 829 bits quando escrito em binário), foi fatorado usando a peneira do corpo numérico em 2020. O cálculo exigiu milhares de anos-núcleo de CPU, distribuídos por dezenas de milhares de máquinas ao redor do mundo. Aqui podemos apreciar esse esforço verificando a solução.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

A segurança do criptossistema de chave pública RSA baseia-se na dificuldade computacional da fatoração de inteiros, no sentido de que um algoritmo eficiente para a fatoração de inteiros o quebraria.

A seguir, vamos considerar um problema relacionado, mas muito diferente: calcular o máximo divisor comum (ou MDC) de dois inteiros.

Máximo divisor comum (MDC)

Entrada: inteiros não negativos $N$ e $M,$ sendo pelo menos um deles positivo
Saída: o máximo divisor comum de $N$ e $M$

O máximo divisor comum de dois números é o maior inteiro que divide ambos de forma exata.

Este problema é fácil de resolver com um computador — tem aproximadamente o mesmo custo computacional que multiplicar os dois números de entrada. A função gcd do módulo math do Python calcula o máximo divisor comum de números consideravelmente maiores do que o RSA1024 em um piscar de olhos. (De fato, o RSA1024 é o MDC dos dois números neste exemplo.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Isso é possível porque temos algoritmos muito eficientes para calcular MDCs, o mais conhecido dos quais é o algoritmo de Euclides, descoberto há mais de 2.000 anos.

Poderia existir um algoritmo rápido para a fatoração de inteiros que ainda não descobrimos, permitindo que números grandes como o RSA1024 sejam fatorados em um piscar de olhos? A resposta é sim. Embora possamos esperar que um algoritmo eficiente para fatoração, tão simples e elegante quanto o algoritmo de Euclides para calcular MDCs, já tivesse sido descoberto, não há nada que descarte a existência de um algoritmo clássico muito rápido para a fatoração de inteiros, além do fato de que não conseguimos encontrá-lo até agora. Um poderia ser descoberto amanhã — mas não prenda a respiração. Gerações de matemáticos e cientistas da computação têm buscado, e fatorar números como o RSA1024 ainda está além do nosso alcance.