Fattorizzazione
Fattorizzare un numero n (il termine più corretto sarebbe "ridurre in fattori") significa trovare un insieme di numeri {a0, a1, a2, a3...} tali che la loro moltiplicazione sia il numero originario (n = a0 * a1 * a3 * a3...).La maggior parte dei numeri ha svariate fattorizzazioni possibili, per questo ci si concentra su una tra tutte, che è anche la più importante: la fattorizzazione in numeri primi, che consiste di cercare un insieme di numeri che siano tutti numeri primi (generalmente indicati con {p0, p1, p2, p3...} per ricordare la loro primalità ogni numero naturale ha una ed una sola fattorizzazione in numeri primi.
Nel corso della storia sono stati ideati molti metodi per rendere la fattorizzazione un problema sempre più veloce ed agevole, ma rimane tuttora un problema complesso: ; metodo forza bruta : si divide n per tutti i numeri che gli sono minori ; metodo forza bruta migliorato : utilizzando conoscenze specifiche del problema proposto si può migliorarne il metodo provando a dividere solo per i numeri primi minori o uguali della radice quadrata del numero (numeri primi che possono essere generati efficentemente con un crivello di Eratostene) Recentemente, l'interesse per questo argomento si è acceso improvvisamente nel 1994 grazie a una killer application davvero notevole, escogitata dal matematico Peter Shor: un algoritmo che permette di fattorizzare in tempo polinomiale (cubico, per la precisione) numeri composti anche da centinaia di cifre. Confronta Erik Boni su http://www.zeusnews.it/index.php3?ar=stampa&cod=2110&numero=999
