O Problema da Fatoração de Inteiros (PFI), ou Integer Factoring Problem (IFP), consiste em, dado \(n\) produto de dois primos, obter os primos \(p\) e \(q\) tais que \[ n = p \cdot q \]
Até hoje não foi desenvolvido nenhum algoritmo clássico eficiente (i.e. de complexidade polinomial) para resolver o Problema da Fatoração. Por outro lado, na computação quântica, o algoritmo de Shor pode ser usado para resolvê-lo de forma eficiente.
Os algoritmos de uso especial, ou algoritmos de Primeira Categoria, são algoritmos de fatoração cujo tempo de execução depende de alguma propriedade especial dos fatores de \(n\), por exemplo, o mínimo entre eles.
O algoritmo de divisão por tentativa (ou trial division) consiste em sucessivamente tentar dividir \(n\) por cada um dos primos menores que \(\sqrt{ n }\). Esse é o algoritmo de fatoração mais simples, mas também o menos eficiente.
Note que o tempo de execução desse algoritmo depende não do tamanho de \(n\), mas sim do tamanho do menor dos fatores de \(n\), que será o primeiro a ser encontrado.
O Método da Fatoração em Curvas Elípticas (ou Elliptic Curve Method, ECM) utiliza de Curvas Elípticas para realizar a fatoração de maneira rápida, com complexidade subfatorial (mas ainda exponencial).
Ele é o terceiro melhor método para fatoração de inteiros quaisquer (atrás do QS e do GNFS), e é o melhor para fatorar números que são produtos de vários primos, especialmente se um desses primos for pequeno (até 80 bits, ou 25 dígitos decimais).
Os algoritmos de uso geral, ou algoritmos de Segunda Categoria, são algoritmos de fatoração cujo tempo de execução depende exclusivamente do tamanho de \(n\).
O segundo melhor algoritmo de fatoração conhecido1 é o Crivo Quadrático, ou Quadratic Sieve (QS). Conjectura-se que este algoritmo tenha complexidade média \[ \exp \left\{ (1+ o(n)) \sqrt{ \ln n \cdot \ln(\ln n) } \ \right\} \]
O melhor algoritmo de fatoração conhecido2 é o Crivo de Corpo Numérico Geral, ou General Number Field Sieve (GNFS), também chamado de Crivo de Corpo Geral, ou General Field Sieve (GFS). Conjectura-se que este algoritmo tenha complexidade média \[ \exp \left\{ \left( \left( \frac{64}{9} \right)^{1/3} + o(1) \right) (\ln n)^{1/3}(\ln \ln n)^{2/3} \right\} \]