Crivo do corpo de números generalizado
Na teoria dos números, o Crivo do corpo de números generalizado (GNFS, do inglês general number field sieve) é o algoritmo clássico mais eficiente conhecido para a fatoração de inteiros maiores que um 10100. Heuristicamente, sua complexidade para fatorar um inteiro n (consistindo em ⌊log2 n⌋ + 1 bits) é da forma
Suponha que f seja um polinômio de grau k sobre Q {\textstyle \mathbb {Q} } (os números racionais), e r seja uma raiz complexa de f. Então, f(r) = 0, o que pode ser rearranjado para expressar rk como uma combinação linear de potências de r menores que k. Esta equação pode ser usada para reduzir quaisquer potências de r com expoente e ≥ k. Por exemplo, se f(x) = x2 + 1 e r for a unidade imaginária i, então i2 + 1 = 0, ou i2 = −1. Isso nos permite definir o produto complexo: Em geral, isso leva diretamente ao corpo de números algébricos Q [ r ] {\textstyle \mathbb {Q} [r]} , que pode ser definido como o conjunto de números complexos dado por: O produto de quaisquer dois desses valores pode ser calculado tomando o produto como polinômios, e então reduzindo quaisquer potências de r com expoente e ≥ k conforme descrito acima, produzindo um valor na mesma forma. Para garantir que este corpo seja de fato de dimensão k e não colapse para um corpo ainda menor, é suficiente que f seja um polinômio irredutível sobre os racionais. Da mesma forma, pode-se definir o anel de inteiros O Q [ r ] {\textstyle \mathbb {O} _{\mathbb {Q} [r]}} como o subconjunto de Q [ r ] {\textstyle \mathbb {Q} [r]} cujos elementos são raízes de polinômios mônicos com coeficientes inteiros. Em alguns casos, este anel de inteiros é equivalente ao anel Z [ r ] {\textstyle \mathbb {Z} [r]} . No entanto, existem muitas exceções.
Escolha do polinômio
Dois polinômios f(x) e g(x) de graus pequenos d e e são escolhidos, os quais têm coeficientes inteiros, são irredutíveis sobre os racionais e que, quando interpretados sob a módulo n, têm uma raiz inteira comum m. Não é conhecida uma estratégia ideal para escolher esses polinômios; um método simples é obter f da expansão na base-m de n para uma escolha apropriada de m. Mais precisamente: para qualquer escolha de m, escrever n na base m é, por definição, encontrar os dígitos a 0 , a 1 , … , a d {\textstyle a_{0},a_{1},\ldots ,a_{d}} onde 0 ≤ a i < m {\textstyle 0\leq a_{i}<m} para cada i, de tal forma que o que, por sua vez, significa que m é uma raiz do polinômio f ( x ) = a d x d + ⋯ + a 1 x + a 0 {\textstyle f(x)=a_{d}x^{d}+\cdots +a_{1}x+a_{0}} módulo n. Para os propósitos do crivo geral do corpo de números, primeiro fixamos um grau apropriado d e então realizamos a expansão acima para uma série de valores m de ordem n1/d, após o qual escolhemos o polinômio f como aquele cujos coeficientes são, no geral, os menores entre os candidatos obtidos desta forma. Em seguida, simplesmente definimos g ( x ) = x − m {\textstyle g(x)=x-m} .
Geração de pares de relações (crivagem)
Considere os anéis de corpo de números Z[r1] e Z[r2], onde r1 e r2 são raízes dos polinômios f e g. Como f é de grau d com coeficientes inteiros, se a e b forem inteiros, também o será bd·f(a/b), que chamamos de r. De forma semelhante, s = be·g(a/b) é um inteiro. O objetivo é encontrar valores inteiros de a e b que tornem simultaneamente r e s suaves em relação à base de primos escolhida. Se a e b forem pequenos, então r e s também serão pequenos, aproximadamente do tamanho de m, e teremos uma chance melhor de que eles sejam suaves ao mesmo tempo. A abordagem atual mais conhecida para esta pesquisa é a crivagem em reticulado (lattice sieving); para obter rendimentos aceitáveis, é necessário usar uma grande base de fatores. Esses pares também são chamados de "relações".
Pós-processamento
Tendo pares suficientes como esses, usando a eliminação de Gauss, pode-se fazer com que produtos de certos r e dos correspondentes s sejam quadrados ao mesmo tempo. Uma condição ligeiramente mais forte é necessária — que eles sejam normas de quadrados em nossos corpos de números, mas essa condição também pode ser alcançada por este método. Cada r é uma norma de a − r1b e, consequentemente, o produto dos fatores correspondentes a − r1b é um quadrado em Z[r1], com uma "raiz quadrada" que pode ser determinada (como um produto de fatores conhecidos em Z[r1]) — tipicamente, será representada como um número algébrico irracional. De forma semelhante, o produto dos fatores a − r2b é um quadrado em Z[r2], com uma "raiz quadrada" que também pode ser calculada. Deve-se notar que o uso da eliminação de Gauss não fornece o tempo de execução ideal do algoritmo. Em vez disso, são usados algoritmos de resolução de matrizes esparsas, como o algoritmo Lanczos em bloco ou Wiedemann em bloco.
Computação distribuída
O GNFS envolve grandes quantidades de computação e requer alguma forma de computação distribuída para ser concluído em prazos práticos, dado números grandes como o RSA-768. As seguintes etapas podem ser feitas em paralelo: O teste de caráter quadrático pode ser aplicado aos resultados da resolução da matriz para identificar soluções verdadeiras. No caso do RSA-768, 460 de 512 eram verdadeiras. Oito delas foram selecionadas para a etapa da raiz quadrada, produzindo 5 fatorações idênticas na etapa final após uma quantidade comparativamente pequena de computação. Uma descrição mais aprofundada de um esforço distribuído pode ser encontrada para RSA-240, DLP-240 e RSA-250, usando o software CADO-NFS. Os arquivos de reprodução completos são fornecidos em um repositório vinculado no apêndice do artigo.
Algumas implementações se concentram em uma classe menor de números. Estas são conhecidas como técnicas do crivo especial do corpo de números (SNFS), como as usadas no Projeto Cunningham. Até 2007, a implementação padrão-ouro era um conjunto de software desenvolvido e distribuído pelo CWI nos Países Baixos, que estava disponível apenas sob uma licença relativamente restritiva.[carece de fontes?] Em 2007, Jason Papadopoulos desenvolveu uma implementação mais rápida do processamento final como parte do msieve, que é de domínio público. Ambas as implementações apresentam a capacidade de serem distribuídas entre vários nós em um cluster com uma interconexão suficientemente rápida.
Computação voluntária
Um projeto chamado NFSNET funcionou de 2002 a, pelo menos, 2007. Ele usou computação distribuída voluntária na Internet. Paul Leyland do Reino Unido e Richard Wackerbarth do Texas estiveram envolvidos. Uma tentativa mais recente chamada NFS@Home continua em execução em setembro de 2025. Historicamente, usou versões modificadas do msieve. Geralmente, utiliza crivos especiais do corpo de números.
