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 il loro prodotto sia il numero originario (n = a0 * a1 * a3 * a3...).
Se un numero ha come proprio unico fattore se stesso, è un numero primo (Ad es: 5=51).
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 nel cercare un insieme di numeri che siano tutti 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.
Ad esempio
52=22×131
oppure
3300=22×31×52×111
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
- si considerano solo i numeri primi minori o uguali alla radice quadrata del numero (possono essere generati efficentemente con un crivello di Eratostene), si prova a dividere il numero n per il minore di questi, se non risulta divisibile si procede con il successivo e così via,si procede allo stesso modo con il risultato ottenuto e si ripete la stessa sequenza fino a quando si ottiene quoziente 1. Se tutti i numeri primi minori della radice quadrata di n sono stati provati e nessuno di loro è un divisore, n stesso è un numero primo. Questa procedura diventa via via più lunga al crescere del numero da fattorizzare.
- Curve ellittiche
- come per i test di primalità, esistono algoritmi statistici (ECM) che aiutano a fattorizzare un numero, con errore che può essere reso piccolo a piacere. I più noti sono l'algoritmo di Pollard e quello di Lenstra.
Il più veloce algoritmo totalmente deterministico è l'algoritmo di Pollard - Strassen.
Nel 1994 Peter Shor ha mostrato un algoritmo di fattorizzazione in tempo polinomiale (cubico, per la precisione). L'unico problema è che richiede un computer quantistico.
Bibliografia
Montgomery, P. L. "Speeding up the Pollard and Elliptic Curve Methods of Factorization." Math. Comput. 48, 243-264, 1987.