Fattorizzazione

Fattorizzare un numero $n$ (il termine più corretto sarebbe "ridurre in fattori") significa trovare un insieme di numeri $\{a_0, a_1, a_2, a_3 \dots\}$ tali che il loro prodotto sia il numero originario ($n = a_0 \times a_1 \times a_2 \times a_3 \times \dots$).

Numeri primi e fattorizzazione

Innanzitutto bisogna tenere presente che un qualunque numero naturale ha infinite fattorizzazioni: lo si può infatti moltiplicare quante volte si vuole per 1. In pratica, però, non si considerano i fattori 1 nella fattorizzazione: è questa tra l'altro la ragione per cui si preferisce affermare che 1 non è un numero primo, anche se soddisferebbe la definizione "è divisibile solamente per sé stesso e per 1".

La maggior parte dei numeri ha comunque svariate fattorizzazioni possibili: ad esempio, $24 = 2\times 12 = 2\times 3\times 4 = 3\times 8 = 2\times 2\times 2\times 3$. Per convenzione, ci si concentra su una sola tra tutte queste, che è anche la più importante: la fattorizzazione in numeri primi, che consiste nel cercare un insieme di fattori del numero che siano tutti primi (generalmente indicati con $\{p_0, p_1, p_2, p_3 \dots\}$ per ricordare la loro primalità); ogni numero naturale ha una ed una sola fattorizzazione in numeri primi. Ad esempio

$12 = 2^2 \times 3^1$

$52 = 2^2 \times 13^1$

$3300 = 2^2 \times 3^1 \times 5^2 \times 11^1$

Metodi di fattorizzazione

Nel corso della storia sono stati ideati molti metodi per rendere la fattorizzazione un problema sempre più veloce ed agevole: esso però rimane tuttora un problema complesso.

• metodo forza bruta: si divide n per tutti i numeri che gli sono minori. Il costo operativo nel caso peggiore è O(n)
• metodo forza bruta migliorato: si considerano solo i numeri primi minori o uguali alla radice quadrata del numero (possono essere generati efficientemente 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. Il costo operativo nel caso peggiore è O(√n) (nell'assunzione poco reale di un modello di costo a costi costanti).
• metodo delle curve ellittiche (ECM): uno dei più noti è quello di Lenstra, che si basa su idee già contenute nel "(p-1)-method" di Pollard. Insieme all'algoritmo di Pollard-Strassen e al Crivello dei campi di numeri generale è a tutt'oggi (2007) uno dei più veloci metodi totalmente deterministici.
• metodi probabilistici: Tra di essi ci sono gli algoritmi di Schnorr-Lenstra e di Lenstra-Pomerance.

Nel 1994 Peter Shor ha mostrato un algoritmo di fattorizzazione di un numero n in tempo polinomiale (cubico, per la precisione) nel numero di cifre necessarie per rappresentare n. 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.

Voci correlate

• Scomposizione dei polinomi
• Fattorizzazione (teoria degli anelli)

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