Crivello dei campi di numeri generale

In matematica, il crivello dei campi di numeri generale (noto anche semplicemente come crivello dei campi di numeri o anche GNFS, dall'inglese general number field sieve) è il più efficiente algoritmo classico conosciuto per fattorizzare gli interi con più di 100 cifre. Euristicamente, la sua complessità computazionale, per fattorizzare un intero n è

${\displaystyle O\left(e^{(c+o(1))(\log n)^{\frac {1}{3}}(\log \log n)^{\frac {2}{3}}}\right)}$

(vedi notazione O grande), ove c è una costante che dipende dalla variante dell'algoritmo utilizzata.^[1] È una generalizzazione del crivello dei campi di numeri speciale. A differenza di quest'ultimo che può essere utilizzato solo su numeri di una particolare forma, il crivello dei campi di numeri generale può essere utilizzato per fattorizzare ogni numero (ad eccezione delle potenze dei primi, che però si possono fattorizzare facilmente con altri metodi).

Il crivello dei campi di numeri (sia generale che speciale) può essere considerato un'estensione del più semplice rational sieve. Per fattorizzare un intero grande n, quest'ultimo algoritmo ha bisogno di trovare numeri dello stesso ordine di n che hanno fattori primi piccoli; la rarità di questi numeri rende di fatto inutilizzabile il rational sieve. Per ovviare a questo problema, il crivello dei campi di numeri sposta il problema negli anelli degli interi di alcuni campi di numeri. Questo approccio, pur introducendo alcune complicazioni teoriche, rende sufficiente cercare gli interi con fattori primi piccoli tra i numeri di ordine n^1/d, ove d è un intero maggiore di 1. Dato che i numeri più piccoli hanno generalmente fattori primi più piccoli, questa modifica aumenta notevolmente l'efficienza del metodo.

Si noti che log n è essenzialmente il numero di cifre nella rappresentazione binaria di n e di conseguenza, nei casi peggiori, il tempo necessario per compiere una fattorizzazione è più che polinomiale (nel numero delle cifre). Non è ancora noto, se esistono degli algoritmi per computer classici che risolvono il problema della fattorizzazione in un tempo polinomiale, mentre ne è stato trovato uno, l'algoritmo di fattorizzazione di Shor, che risolve il problema per i computer quantistici.

• (EN) Eric W. Weisstein, Crivello dei campi di numeri generale, su MathWorld, Wolfram Research.
• Arjen K. Lenstra e H. W. Lenstra, Jr. "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). 2nd edition, Springer. ISBN 0-387-25282-7. Sezione 6.2: Number field sieve, pp. 278–301.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica