La fattorizzazione dei numeri interi
Esistono diversi metodi per fattorizzare un numero intero. Quasi tutti sono algoritmi con complessità non polinomiale ( problemi difficili ).
Il crivello di Eratostene
La fattorizzazione tramite il crivello di Eratostene s i basa sul seguente algoritmo:
- Divido un numero n per a=2,3,4,5,..., √n
- Quando il numero n è divisibile per a, vale n=a·m
- Aggiungo a alla lista dei fattori
- Ricomincio l'algoritmo con n=m
L'algoritmo termina quando il numero n è uguale a 1.
Esempio
Calcolo la fattorizzazione del numero 28
$$ n = 28 $$
$$ 2|28 \Rightarrow n = \frac{28}{2} = 14 , f = \{2\} $$
Ricomincio con n=14
$$ 2|14 \Rightarrow n = \frac{14}{2} = 7 , f = \{2,2\} $$
Ricomincio con n=7
$$ 1|7 \\ 2|7 \\ 3|7 \\ 4|7 \\ 5|7 \\ 6|7 \\ 7|7 \Rightarrow n = \frac{7}{7} = 1 , f = \{2,2,7\} $$
L'algoritmo termina qui perché n=1.
I fattori del numero 28 sono
$$ 2 \cdot 2 \cdot 7 $$
$$ 2^2 \cdot 7 $$
Nota. Questo metodo è utile per i numeri interi molto piccoli. Tuttavia, dal punto di vista computazionale diventa un problema difficile (non polinomiale) nel caso dei numeri molto grandi.
Il metodo di Fermat
Il metodo di Fermat è un altro metodo per ridurre in fattori i numeri interi ma si applica solo per i numeri dispari.
- Calcolo il valore assoluto [ ] della radice del numero n e aggiungo +1 $$ k = [ \sqrt{9} ] +1 $$
- Verifico se la differenza tra il quadrato di k e n è un quadrato perfetto $$ x = k^2 - n $$
- Se è un quadrato perfetto ottengo la fattorizzazione del numero n con il prodotto $$ (x+k) \cdot (x-k) $$
- Se non è un quadrato perfetto, incremento k di +1 e ricalcolo x finché non trovo un quadrato perfetto.
Il risultato è la fattorizzazione del numero dispari.
Non necessariamente è una fattorizzazione in primi.
Nota. Il metodo di Fermat è più efficiente rispetto al metodo di Eratostene. In particolar modo per fattorizzare i numeri molto grandi. In ogni caso, è comunque un algoritmo con complessità esponenziale.
Esempio
Il numero intero dispari da fattorizzare è
$$ n = 69 $$
Calcolo il valore k
$$ k= \sqrt{n} + 1 = [ \sqrt{69} ] + 1 = 8+1 = 9 $$
Le parentesi quadre indicano il valore assoluto della radice.
Poi verifico se k^2 - n è un quadrato perfetto
$$ x=k^2-n = 9^2 - 69 = 81 - 69 = 12 $$
Il numero 12 non è un quadrato perfetto.
Pertanto aumento k di 1 finché non trovo un quadrato perfetto (x).
$$ x=(10)^2-n - 69 = 10^2-69 = 31 $$
$$ x=(11)^2-n - 69 = 11^2-69 = 52 $$
$$ x=(12)^2-n - 69 = 12^2-69 = 75 $$
$$ x=(13)^2-n - 69 = 13^2-69 = 10 $$
Ho trovato un quadrato perfetto (100) con k=13 e x=10.
Quindi la riduzione in fattori del numero 69 è
$$ (k-x)·(k+x) $$
$$ (13-10)·(13+10) $$
$$ (3)·(23) $$
Ho trovato la fattorizzazione del numero 69.
Nota. La fattorizzazione con il metodo di Fermat non necessariamente deve essere in numeri primi.
E così via.
