Archivi Categorie: Teoria e pratica

Il problema della fattorizzazione

NP

Hronir ci fa un piacere ricordandoci in un paio di ottimi post che il problema della fattorizzazione dei numeri non è necessariamente un problema NP (non polinomiale). Da leggere attentamente!

Il fatto è che molte persone, anche molti ricercatori in matematica, informatica, etc. danno per scontato che:

  1. La fattorizzazione sia un problema NP-completo, e quindi gli algoritmi di crittografia, basati sul problema della fattorizzazione, siano intrinsicamente sicuri.
  2. I calcolatori quantistici renderanno i problemi NP-hard risolvibili in tempo polinomiale, e quindi renderanno inutili gli attuali algoritmi di crittografia.

In quanto al primo assunto, in realtà non si sa quale sia la complessità del problema di fattorizzazione. Hronir da degli ottimi link, vi consiglio di seguirli. Il sospetto è che in realtà non sia un problema NP-completo, ma un problema un po’ più semplice (magari non proprio polinomiale, ma insomma). In quanto al secondo assunto, Hronir ci dice che non esiste (ad oggi) alcun algoritmo quantistico in grado di risolvere un problema NP-hard.

Non ci avete capito una mazza? E’ il momento di iscriversi a un corso di informatica! 🙂

Altri link utili: