Fattorizzazione

Da Wikipedia, l'enciclopedia libera.

In matematica la fattorizzazione è la riduzione in fattori: fattorizzare un numero n 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[modifica | modifica wikitesto]

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 se 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[modifica | modifica wikitesto]

Nel corso della storia sono stati ideati molti algoritmi per rendere la fattorizzazione un problema sempre più veloce. Il problema però rimane tuttora un problema complesso. Tra i metodi utilizzati vi sono i seguenti:

  • 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).
  • metodi di fattorizzazione basati su curve ellittiche (ECM, dall'inglese Elliptic Curve Method): uno dei più noti è quello di Lenstra, che si basa su idee già contenute nell'algoritmo (p-1) 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 sviluppato un algoritmo di fattorizzazione polinomiale (cubico, per la precisione). Questo algoritmo, noto come algoritmo di fattorizzazione di Shor, richiede tuttavia un computer quantistico.

Bibliografia[modifica | modifica wikitesto]

  • Montgomery, P. L. "Speeding up the Pollard and Elliptic Curve Methods of Factorization." Math. Comput. 48, 243-264, 1987.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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