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 $⌊log 2 n ⌋ + 1$ bits) é da forma

{\begin{aligned}&\exp \left(\left((64/9)^{1/3}+o(1)\right)\left(\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)\\[5pt]={}&L_{n}\left[1/3,(64/9)^{1/3}\right]\end{aligned}}

na notação Big-O e na notação L.^[1] É uma generalização do crivo especial do corpo de números: enquanto o último só pode fatorar números de uma certa forma especial, o crivo geral do corpo de números pode fatorar qualquer número, exceto potências de números primos (que são triviais de fatorar extraindo as raízes).

O princípio do crivo do corpo de números (tanto especial quanto geral) pode ser entendido como uma melhoria em relação ao crivo racional ou ao crivo quadrático, que são mais simples. Ao usar tais algoritmos para fatorar um número grande $n$ , é necessário procurar por números suaves (ou seja, números com fatores primos pequenos) da ordem de $n 1/2$ . O tamanho desses valores é exponencial em relação ao tamanho de $n$ (veja abaixo). O crivo geral do corpo de números, por outro lado, consegue procurar por números suaves que são subexponenciais em relação ao tamanho de $n$ . Como esses números são menores, é mais provável que sejam suaves do que os números inspecionados em algoritmos anteriores. Esta é a chave para a eficiência do crivo do corpo de números. A fim de alcançar essa aceleração, o crivo do corpo de números tem que realizar computações e fatorações em corpos de números. Isso resulta em muitos aspectos bastante complicados do algoritmo, em comparação com o crivo racional mais simples.

O tamanho da entrada para o algoritmo é $log 2 n$ ou o número de bits na representação binária de $n$ . Qualquer elemento da ordem $n c$ para uma constante $c$ é exponencial em $log n$ . O tempo de execução do crivo do corpo de números é superpolinomial, mas subexponencial no tamanho da entrada.

Corpos de números

Suponha que $f$ seja um polinômio de grau $k$ sobre ${\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 $r k$ 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 \geq k$ . Por exemplo, se $f (x) = x 2 + 1$ e $r$ for a unidade imaginária $i$ , então $i 2 + 1 = 0$ , ou $i 2 = -1$ . Isso nos permite definir o produto complexo:

{\begin{aligned}(a+bi)(c+di)&=ac+(ad+bc)i+(bd)i^{2}\\[4pt]&=(ac-bd)+(ad+bc)i.\end{aligned}}

Em geral, isso leva diretamente ao corpo de números algébricos ${\textstyle \mathbb {Q} [r]}$ , que pode ser definido como o conjunto de números complexos dado por:

a_{k-1}r^{k-1}+\cdots +a_{1}r^{1}+a_{0}r^{0},{\text{ onde }}a_{0},\ldots ,a_{k-1}\in \mathbb {Q} .

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 \geq 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 ${\textstyle \mathbb {O} _{\mathbb {Q} [r]}}$ como o subconjunto de ${\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 ${\textstyle \mathbb {Z} [r]}$ . No entanto, existem muitas exceções.^[2]

Método

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 ${\textstyle a_{0},a_{1},\ldots ,a_{d}}$ onde ${\textstyle 0\leq a_{i}<m}$ para cada i, de tal forma que

n=a_{d}m^{d}+\cdots +a_{1}m+a_{0}

,

o que, por sua vez, significa que m é uma raiz do polinômio ${\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 n^1/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 ${\textstyle g(x)=x-m}$ .

Melhorando a escolha do polinômio

A escolha do polinômio pode afetar drasticamente o tempo para concluir o restante do algoritmo. O método de escolha de polinômios baseado na expansão de $n$ na base $m$ mostrado acima é abaixo do ideal em muitas situações práticas, levando ao desenvolvimento de métodos melhores.

Um desses métodos foi sugerido por Murphy e Brent;^[3] eles introduzem uma pontuação em duas partes para os polinômios, baseada na presença de raízes módulo pequenos primos e no valor médio que o polinômio assume sobre a área de crivagem.

Os melhores resultados relatados^[4] foram alcançados pelo método de Thorsten Kleinjung,^[5] que permite $g (x) = ax + b$ , e realiza a busca sobre um $a$ composto por fatores primos pequenos congruentes a 1 módulo 2 $d$ e sobre os coeficientes principais de $f$ que são divisíveis por 60.

Geração de pares de relações (crivagem)

Considere os anéis de corpo de números Z[r₁] e Z[r₂], onde r₁ e r₂ 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á b^d·f(a/b), que chamamos de r. De forma semelhante, s = b^e·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".^[6]

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 − r₁b e, consequentemente, o produto dos fatores correspondentes a − r₁b é um quadrado em Z[r₁], com uma "raiz quadrada" que pode ser determinada (como um produto de fatores conhecidos em Z[r₁]) — tipicamente, será representada como um número algébrico irracional. De forma semelhante, o produto dos fatores a − r₂b é um quadrado em Z[r₂], 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.

Como m é uma raiz tanto de f quanto de g mod n, existem homomorfismos dos anéis Z[r₁] e Z[r₂] para o anel Z/nZ (os inteiros módulo n), que mapeiam r₁ e r₂ para m, e esses homomorfismos mapearão cada "raiz quadrada" (tipicamente não representada como um número racional) em seu representante inteiro. Agora, o produto dos fatores a − mb mod n pode ser obtido como um quadrado de duas maneiras — uma para cada homomorfismo. Assim, pode-se encontrar dois números x e y, com x²−y² divisível por n e, novamente, com probabilidade de pelo menos um meio, obtemos um fator de n encontrando o máximo divisor comum de n e x − y.

A etapa de pós-processamento envolve grandes quantidades de dados gerados a partir das duas etapas anteriores. Praticamente, ela é feita dividindo-a em três fases:^[6]

Filtragem: analisa as relações para encontrar uma coleção que seja suficiente para construir uma matriz. É possível que esta etapa falhe se não houver relações suficientes e é difícil estimar quantas relações são necessárias de antemão. Usar mais relações do que o necessário tende a facilitar as etapas posteriores, produzindo uma matriz menor.
Álgebra linear: procura um grupo de vetores que se encontram no espaço nulo da matriz muito grande produzida na etapa anterior.
Raiz quadrada: pode ser calculada sobre qualquer solução da última etapa.

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:^[7]

Crivagem, que pode produzir relações duplicadas e requer quantidades massivas de computação.
Desduplicação de relações e remoção de relações únicas (singletons).
Álgebra linear, que requer quantidades massivas de computação.

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.^[7]

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.^[8]

Implementações

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.

GGNFS (GNU GPL) de Chris Monico, última atualização em 2005. Pode realizar todas as etapas. Lida com cerca de 160 dígitos para SNFS e 135 dígitos para GNFS. Inclui estas partes também sob GNU GPL:
- pol5: Seleção de polinômios por Kleinjung 2005
- lasieve4: Crivagem em reticulado (lattice sieving) por Franke e Kleinjung 2001–2004
factor by gnfs, código em C++ de Chris DiBona e Chris Card, última atualização em 2024. GNU GPL.
CADO-NFS, implementação em C/C++ de todas as etapas por uma grande equipe do INRIA. Última atualização em 2025 (até 2025). GNU LGPL.
msieve. Contém código de pós-processamento final, uma seleção de polinômio otimizada para números menores e uma implementação do crivo de linha (line sieve). Domínio público.
kmGNFS. Implementação básica de todas as etapas por Christos Bakogiannis e Nikolaos Karapanos, última atualização em 2009.
YAFU. Implementação de todas as etapas por Ben Buhrow. Última atualização em 2025 (até 2025). Domínio público.

Computação voluntária

Um projeto chamado NFSNET funcionou de 2002^[9] a, pelo menos, 2007. Ele usou computação distribuída voluntária na Internet.^[10] Paul Leyland do Reino Unido e Richard Wackerbarth do Texas estiveram envolvidos.^[11]

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.

Notas

↑ Pomerance, Carl (Dezembro de 1996). «A Tale of Two Sieves» (PDF). Notices of the AMS. 43 (12). pp. 1473–1485
↑ Ribenboim, Paulo (1972). Algebraic Numbers. [S.l.]: Wiley-Interscience. ISBN 978-0-471-71804-8
↑ Murphy, B.; Brent, R. P. (1998), «On quadratic polynomials for the number field sieve», Australian Computer Science Communications, 20: 199–213
↑ Franke, Jens (2006), On RSA 200 and larger projects (PDF)
↑ Kleinjung, Thorsten (Outubro de 2006). «On polynomial selection for the general number field sieve» (PDF). Mathematics of Computation. 75 (256): 2037–2047. Bibcode:2006MaCom..75.2037K. doi:10.1090/S0025-5718-06-01870-9. Consultado em 13 de dezembro de 2007
1 2 «readme.nfs from msieve»
1 2 «We are pleased to announce the factorization of RSA768, the following 768-bit, 232-digit number from RSA's challenge list:»
↑ F. Boudot et al, "Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment," 10 de junho de 2020.
↑ Paul Leyland (12 de dezembro de 2003). «NFSNET: the first year». Presentation at EIDMA-CWI Workshop on Factoring Large Numbers. Consultado em 9 de agosto de 2011
↑ «Welcome to NFSNET». 23 de abril de 2007. Consultado em 9 de agosto de 2011. Cópia arquivada em 22 de outubro de 2007
↑ «About NFSNET». Consultado em 9 de agosto de 2011. Cópia arquivada em 9 de maio de 2008

Referências

Arjen K. Lenstra e H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag.
Richard Crandall e Carl Pomerance. Prime Numbers: A Computational Perspective (2001). 2ª edição, Springer. ISBN 0-387-25282-7. Seção 6.2: Number field sieve, pp. 278–301.

Matthew E. Briggs: An Introduction to the General Number Field Sieve, 1998

[1] Pomerance, Carl (Dezembro de 1996). «A Tale of Two Sieves» (PDF). Notices of the AMS. 43 (12). pp. 1473–1485

[AlgNumbersRibenboim-2] Ribenboim, Paulo (1972). Algebraic Numbers. [S.l.]: Wiley-Interscience. ISBN 978-0-471-71804-8

[3] Murphy, B.; Brent, R. P. (1998), «On quadratic polynomials for the number field sieve», Australian Computer Science Communications, 20: 199–213

[4] Franke, Jens (2006), On RSA 200 and larger projects (PDF)

[5] Kleinjung, Thorsten (Outubro de 2006). «On polynomial selection for the general number field sieve» (PDF). Mathematics of Computation. 75 (256): 2037–2047. Bibcode:2006MaCom..75.2037K. doi:10.1090/S0025-5718-06-01870-9. Consultado em 13 de dezembro de 2007

[msieve_readme_nfs-6] 1 2 «readme.nfs from msieve»

[rsa768-7] 1 2 «We are pleased to announce the factorization of RSA768, the following 768-bit, 232-digit number from RSA's challenge list:»

[Boudot240-8] F. Boudot et al, "Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment," 10 de junho de 2020.

[9] Paul Leyland (12 de dezembro de 2003). «NFSNET: the first year». Presentation at EIDMA-CWI Workshop on Factoring Large Numbers. Consultado em 9 de agosto de 2011

[10] «Welcome to NFSNET». 23 de abril de 2007. Consultado em 9 de agosto de 2011. Cópia arquivada em 22 de outubro de 2007

[11] «About NFSNET». Consultado em 9 de agosto de 2011. Cópia arquivada em 9 de maio de 2008

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]