Il problema dell' intera fattorizzazione è il problema computazionale di determinare la prima fattorizzazione di un dato intero. Formulato come un problema decisionale, è il problema di decidere se l' input ha un fattore inferiore a k. Nessun algoritmo efficiente di fattorizzazione dell' intero è noto, e questo fatto costituisce la base di diversi sistemi crittografici moderni, come l' algoritmo RSA. Il problema della fattorizzazione integrale è in NP e in co-NP (e anche in UP e co-UP). Se il problema è NP-completo, la gerarchia temporale polinomiale crollerà al suo primo livello (cioè, NP sarà uguale a co-NP). L' algoritmo più noto per la fattorizzazione di interi è il setaccio a campo numerico generale, che impiega tempo O (e (64/9)1/3 (n. log 2)1/3 (log (n. log 2))2/3) per calcolare un numero intero a n-bit. Tuttavia, l' algoritmo quantistico più conosciuto per questo problema, l' algoritmo di Shor, funziona nel tempo polinomio. Purtroppo, questo fatto non dice molto su dove sta il problema rispetto alle classi di complessità non quantistiche.
Il problema dell' intera fattorizzazione cerca essenzialmente di determinare se il valore di un ingresso è inferiore a quale variabile?
k k k