Teoria dei numeri
Lezione del giorno 11 maggio 2009
L’ algoritmo illustrato nella lezione precedente, che, dato in input un naturale x e fissato un naturale n>1, calcola la parte intera della radice n-esima di x, si può trasformare facilmente in un algoritmo che testi se un numero naturale x sia la potenza n-esima esatta di un opportuna base naturale, dove n è un naturale >1 fissato.
Infatti basta calcolare con l’algoritmo precedente la parte intera yk=y della radice n-esima di x, ed imporre che essa coincida esattamente con la radice n-esima di x, quindi basta aggiungere all’algoritmo una istruzione che esegua il calcolo della potenza ykn e verifichi se il risultato è =x : in caso affermativo x è una potenza n-esima esatta di base naturale, in caso negativo non lo é.
Ovviamente anche tale algoritmo ha complessità polinomiale: si deve aggiungere all’algoritmo precedente solo il calcolo della potenza ykn che, come visto nella lezione precedente, ha complessità di ordine O(r3): quindi in totale l’algoritmo ha ancora complessità polinomiale di ordine O(r4).
Infine possiamo notare che si può costruire un algoritmo che, dato in input un naturale x>1, testi se x è potenza n-esima di un opportuna base naturale, per un opportuno naturale n>1 (notare che n non è fissato a priori).
Infatti abbiamo notato sopra che in ogni caso si ha nlog2x<r (dove r è la lunghezza binaria di x), quindi basta ripetere l’algoritmo precedente per tutti i valori n con 2n<r: se per nessuno di tali valori il test dà esito positivo possiamo concludere con certezza che l’input x non è potenza n-esima di un opportuna base naturale, per nessun naturale n>1; se invece per qualcuno di tali valori n il test dà esito positivo, abbiamo trovato che x è potenza n-esima di un opportuna base naturale.
Poiché l’algoritmo precedente ha complessità di ordine O(r4), ed esso viene ripetuto un numero di volte <r, complessivamente l’algoritmo ha complessità polinomiale di ordine O(r5).
Il test di primalità AKS (Agrawal, Kayal, Safena).
E’ l’unico test di primalità deterministico di complessità polinomiale che si conosca a tutt’oggi.
E’ stato implementato nel 2002 da tre matematici indiani: Agrawal, Kayal, Saxena.
Osserviamo prima di tutto che, se m è un numero primo, i coefficienti binomiali
i
m con 1im-1 sono tutti multipli di m (come già dimostrato nella dimostrazione di un risultato precedente): infatti si ha
i
m =i!(mm!1)! dunque i!(m-1)!
i
m = m!, ossia il numero primo m è divisore del
prodotto i!(m-1)!
i
m , e poiché m non è divisore né di i! né di (m-1)! (che sono prodotti di fattori
<m, dunque non multipli di m), si ha che m è divisore di
i
m .
Su tale osservazione si basa un test di primalità deterministico che ora esporremo.
Dato un naturale m>1 e dati due polinomi f(x), g(x) a coefficienti interi relativi diremo che f(x) è congruo g(x) modulo m se esiste un polinomio h(x) a coefficienti interi relativi tale che si abbia f(x)-g(x)=mh(x). In tale caso scriveremo f(x)g(x) (mod m).
Ovviamente, se ai , bi sono rispettivamente i coefficienti di f(x), g(x) si ha f(x)g(x) (mod m) se e solo se aibi (mod m) per ogni i, dunque la congruenza fra polinomi si riconduce alle congruenze aritmetiche fra i coefficienti numerici dei polinomi
E’ facile verificare che tale relazione di congruenza fra polinomi è una relazione di equivalenza nell’insieme dei polinomi a coefficienti interi relativi, e che gode di proprietà simili a quelle della congruenza fra interi: essa è per esempio compatibile con somma e prodotto, quindi si possono moltiplicare e sommare congruenze fra polinomi modulo m.
Inoltre anche nella congruenza fra polinomi per ogni polinomio f(x) a coefficienti interi relativi si può definire una riduzione modulo m (indicata con f(x)modm) definita come l’unico polinomio che è congruo f(x) modulo m, e in cui tutti i coefficienti sono compresi fra 0 e m-1: la riduzione si può calcolare riducendo modulo m tutti i coefficienti di f(x).
Esempio: la riduzione modulo 3 del polinomio f(x)=5+2x+7x2+11x3 è:
f(x)mod3 = 2+2x+x2+2x3 Teorema.
Dato un numero naturale m>1, ed un naturale a coprimo con m , si ha:
m è primo (x+a)mxm+a (mod m).
Dimostrazione.
() Sia m primo. Sviluppando con la regola di Newton si ha : (x+a)m = i m-i
m 0 i
x i a
m
Confrontando i coefficienti dei polinomi (x+a)m, xm+a (che hanno il coefficiente principale =1) la tesi è che sia:
i
m ai 0 (mod m) per i=1,2,…,m-1; ama (mod m).
La prima proprietà deriva dall’osservazione fatta sopra :
i
m è multiplo di m per i=1,2,…,m-1.
Il fatto che ama (mod m) deriva dal piccolo teorema di Fermat am-11 (mod m), moltiplicando ambo i membri per a.
() Per ipotesi sia
i
m ai 0 (mod m) per i=1,2,…,m-1; ama (mod m). Supponiamo per assurdo che m non sia primo, e sia q un fattore primo di m, con q<m; sia poi qk la massima potenza di q che divide m.
Consideriamo il coefficiente binomiale
q
m =m(m-1)...(mq! -q1) da cui:
q!
q
m = m(m-1)…..(m-q+1).
L’ipotesi
q
m aq 0 (mod m) implica che qk è divisore del prodotto
q
m aq, ma q non divide aq
(perché q non divide a, essendo a,m coprimi): dunque qk è divisore di
q
m .
Essendo q divisore di q!, si ha che qk+1 è divisore di q!
q
m = m(m-1)…..(m-q+1), dunque (essendo qk la massima potenza di q che è divisore di m) q é divisore di uno dei fattori (m-i) con 1iq-1, contraddizione perché q è divisore di m, ma q non è divisore di i se 1iq-1.
Nota: come si vede nella dimostrazione, nell’implicazione () si può omettere l’ipotesi che a,m siano coprimi, poiché la congruenza ama (mod m) è valida anche se a,m non sono coprimi (cioè se m è divisore di a), in quanto ovviamente m sarà in questo caso divisore della differenza am-a . In base all’ultimo teorema si può allora implementare il seguente test di primalità, con input m:
1) si fissa a piacere un intero a, con 1am-1
2) se mcd(a,m)=d>1 allora si esce con output “n è composto”
3) se invece a,m sono coprimi: se (x+a)mxm+a (mod m) si esce con output “n è primo”, altrimenti si esce con output “n è composto”
Dimostriamo che tale test è deterministico. Se l’input m è primo, certamente a,m sono coprimi (le uniche possibilità per il mcd(a,m) sono 1,m, ma m non è divisore di a perché a<m) e nel passo 3) si esce con output “n è primo” per il Teorema precedente. Viceversa, se nell’algoritmo si esce con output “n è primo”, nel passo 2) si deve avere a,m coprimi, dunque nel passo 3) (visto l’output) la congruenza fra polinomi è verificata, ed m è primo per il Teorema precedente.
Esaminiamo la complessità di calcolo dell’algoritmo.
Nel passo 2) si usa l’algoritmo euclideo delle divisioni successive, di complessità polinomiale.
Nel passo 3) si deve verificare la congruenza polinomiale (x+a)mxm+a (mod m), la quale comporta la verifica delle congruenze dei singoli coefficienti dei 2 membri: essi sono polinomi di grado m, e (a parte il coefficiente di grado massimo che è =1 in entrambi) si tratta di verificare m congruenze numeriche, ognuna di complessità polinomiale. Ma il numero di tali congruenze è m<2r (se r è la lunghezza binaria di m), quindi la complessità globale è di ordine esponenziale.
