Fattorizzare un numero n (il termine più corretto sarebbe "ridurre in fattori") significa trovare un insieme di numeri tali che il loro prodotto sia il numero originario (). Indice 1 Numeri primi e fattorizzazione 2 Metodi di fattorizzazione 3 Bibliografia 4 Voci correlate 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 soddisferebbe la definizione "è divisibile solamente per sé stesso e per 1". La maggior parte dei numeri ha comunque svariate fattorizzazioni possibili: ad esempio, . 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 per ricordare la loro primalità); ogni numero naturale ha una ed una sola fattorizzazione in numeri primi. Ad esempio 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(√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. modifica Bibliografia Montgomery, P. L. "Speeding up the Pollard and Elliptic Curve Methods of Factorization." Math. Comput. 48, 243-264, 1987. modifica Voci correlate Scomposizione dei polinomi Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica