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.

Implementazione dell'algoritmo[modifica | modifica wikitesto]

Segue un'implementazione dell'algoritmo per la fattorizzazione in numeri primi.

// Fattorizza 'value' e salva il risultato in 'res'
void factorize(char *res, int value)
{
    res[0] = '\0';
    if (is_prime(value))
    {
        sprintf(res, "%d", value);
        return;
    }
    for (int i = 2; value > 1 && i <= value; ++i)
    {
        if (!is_prime(i)) continue;
        int exp;
        for (exp = 0; value%i==0; value/=i, ++exp);
        if (!exp) continue;
        if (exp > 1) sprintf(res, "%s%d^%d", res, i, exp);
        else sprintf(res, "%s%d", res, i);
        if (value > 1) sprintf(res, "%s * ", res);
    }
    return;
}

bool is_prime(int value)
{
    for (int i = 2; i <= sqrt(value); ++i)
        if (value%i==0) return false;
    return true;
}

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