Teoria dei numeri
Lezione del giorno 15 maggio 2009 Algoritmi di fattorizzazione.
Sono algoritmi che, dato in input un naturale n>1, calcolano tutti i fattori primi di n: a tutt’oggi non è stato trovato un algoritmo di fattorizzazione di complessità polinomiale.
Un algoritmo di fattorizzazione in genere cerca ottenere un obiettivo intermedio: decomporre l’input n nel prodotto n=ab, dove a,b sono naturali (non necessariamente primi) tali che 1<a,b<n (se a,b non esistono, si conclude che n è primo). Una volta trovati a,b l’algoritmo viene riapplicato separatamente ad a,b per decomporli ulteriormente (se possibile): dopo un numero finito di ripetute applicazioni dell’algoritmo, si perviene al calcolo dei fattori primi di n.
Ovviamente un algoritmo “ingenuo” di fattorizzazione consiste (come nel test ingenuo di primalità) nel testare, per ogni naturale a con 2a n, se a è divisore di n, e in caso affermativo porre n=
ab (dove b=n/a): il numero dei test da effettuare è di ordine esponenziale O( 2 k) se k è la lunghezza binaria di n (perché n<2k dunque n< 2k).
Questo algoritmo trova un divisore a di n in tempi di calcolo ragionevoli solo se n ha un fattore relativamente “piccolo”.
Illustriamo ora un algoritmo di fattorizzazione che invece è efficiente se n è prodotto di 2 divisori relativamente “grandi” e “vicini fra loro”.
Algoritmo di fattorizzazione di Fermat.
Supponiamo l’input n dispari: non è una limitazione in un algoritmo di fattorizzazione perché se n è pari, con successive divisioni per 2 si può fattorizzare n nella forma n=2km, con m dispari, e sostituire m al posto di n come input.
L’algoritmo si basa sul seguente risultato, il quale dimostra che fattorizzare n nel prodotto di 2 numeri naturali equivale sostanzialmente a rappresentare n come differenza di 2 quadrati:
Teorema (Fermat).
Sia n un naturale dispari, e siano:
S = { (a,b)NxN / ab, n=ab } T = { (r,s)ZxZ / r>s0, n=r2-s2 }
Allora la funzione f : S T definita da f(a,b)=((a+b)/2,(a-b)/2) è biunivoca.
Dimostrazione:
Si verifica facilmente che f(a,b)T se (a,b)S.
Per dimostrare che f è biunivoca, basta costruire la funzione inversa: definiamo f-1 : T S ponendo f-1(r,s)=(r+s,r-s) (si verifica facilmente che f-1(r,s)S se (r,s)T).
Si verifica infine che le composizioni ff-1, f-1f sono le funzioni identiche di T ed S.
Come conseguenza del teorema precedente, è possibile implementare un algoritmo di fattorizzazione: dato in input un intero dispari n>1, per trovare una fattorizzazione di n nel prodotto di 2 numeri naturali a,b, basta trovare una coppia (r,s)T (quindi r,s interi, r>s0, tali che n=r2-s2) e porre (a,b)=f-1(r,s)=(r+s,r-s).
Per trovare una coppia (r,s)T, possiamo fissare un intero r>0, e cercare un intero s0 tale che si abbia r2-n=s2 : se r2-n =0 allora s=0, n=r2, a=b=r; se invece r2-n >0 si può usare il test già esaminato in precedenza per verificare se il numero naturale r2-n è un quadrato perfetto di base naturale opportuna s.
Dovendo essere r2-n=s20, si ha r n, dunque il valore minimo da fissare per r è r= n. (è il cosiddetto ceiling di n, ossia il minimo intero n).
Per quanto riguarda il valore massimo di r, notiamo che al crescere di r, cresce il valore corrispondente di a (se esiste) nella coppia (a,b): se r1>r, e se n=r2-s2=r12-s12 , allora s1>s, dunque a=r+s<a1=r1+s1 . Poiché in una fattorizzazione non banale di n (dispari) il valore (teorico) massimo di a è a=n/3 (con b=3), e ricordando che r=(a+b)/2, si ottiene che il valore massimo per r è la parte intera di [(n/3)+3]/2=(n+9)/6.
Dunque, l’algoritmo di fattorizzazione di Fermat si può implementare nel modo seguente:
- input n intero dispari >1
- per r= n, n +1,……, (n+9)/6 si testa se r2-n è un quadrato perfetto di base s0 e in caso affermativo si esce con output “n=ab dove a=r+s, b=r-s”
- se nel ciclo precedente nessun test ha avuto esito positivo, si esce con output “n è primo”
Notiamo anche, come già premesso, che il test di Fermat trova un fattore non banale di n in tempi ragionevoli se n è prodotto di 2 divisori a,b “abbastanza grandi” e “vicini fra loro” perché in tale caso a,b n, dunque r=(a+b)/2 n, ossia il valore r che nel ciclo permette di trovare la fattorizzazione di n è “vicino” alla radice quadrata di n, e dunque (partendo dal valore iniziale r=
n) tale valore viene trovato relativamente “presto”.
Esempio.
Se l’input é n=6077, n=78, (n+9)/6=1014, il ciclo si dovrà eseguire per r=78, 79,…., 1014 e si ha:
r=78 r2-n =7 (non quadrato) r=79 r2-n =164 (non quadrato) r=80 r2-n =323 (non quadrato) r=81 r2-n =484 =222
ottenendo la fattorizzazione n=ab dove a=r+s=81+22=103, b=r-s=81-22=59.
