Fattorizzazione

Da Wikipedia, l'enciclopedia libera.

(Reindirizzamento da Fattore)
Da fare
La pagina di discussione contiene dei suggerimenti per migliorare la voce: 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).

[modifica] 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 soddisfarebbe 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

[modifica] 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(\sqrt{n}).
  • 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 "General Number Field Sieve" è 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 in tempo polinomiale (cubico, per la precisione). L'unico problema è che richiede un computer quantistico.

[modifica] Bibliografia

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


Estratto da "http://it.wikipedia.org/wiki/Fattorizzazione"
Strumenti personali