 xa  xa

(1)

Teoria dei numeri

Lezione del giorno 13 maggio 2009

Abbiaamo osservato che il test deterministico di primalità derivato dal:

Teorema.

Dato un numero naturale m>1, ed un naturale a coprimo con m , si ha:

m è primo  (x+a)

^m

x

^m

+a (mod m).

è di complessità esponenziale, dunque non più efficiente di altri test di primalità già esaminati.

L’idea alla base del test AKS è però quella di “diminuire” il numero dei coefficienti da confrontare nelle congruenze, sfruttando il concetto di “riduzione” di un polinomio modulo un polinomio della forma x

^s

-1.

Dati 3 polinomi f(x), g(x), h(x) a coefficienti interi relativi, diremo che f(x) è congruo g(x) modulo h(x) se la differenza f(x)-g(x) è un polinomio multiplo di h(x), cioè se esiste un polinomio s(x) a coefficienti interi relativi tale che f(x)-g(x)=h(x)s(x). In tale caso scriveremo f(x)g(x) (mod h(x)).

E’ facile verificare che tale relazione di congruenza è una relazione di equivalenza nell’insieme dei polinomi a coefficienti interi relativi, e che gode di proprietà simili a quelle della congruenza fra interi: si possono per esempio moltiplicare e sommare congruenze fra polinomi modulo h(x).

Possiamo notare che la congruenza fra 2 polinomi f(x), g(x) modulo un intero m>1, introdotta in precedenza, è un caso particolare: infatti f(x)g(x) (mod m) equivale a f(x)g(x) (mod h(x)), dove h(x) è il polinomio costante h(x)=m.

Un caso particolare della congruenza modulo h(x) si ha se il polinomio h(x) ha la forma h(x)=x

^r

-1, con esponente r naturale.

In tale caso se x

^k

è una qualunque potenza di x ad esponente intero k0, e se dividiamo k per r con quoziente q e resto t, si ottiene k=rq+t, con 0t<r, da cui x

^k

-x

^t

=x

^rq

x

^t

-x

^t

=x

^t

(x

^rq

-1), e tenendo conto che x

^rq

-1 è multiplo di x

^r

-1 (basta sfruttare l’identità (x

^r

)

^q

-1=(x

^r

-1)(x

^r(q-1)

+x

^r(q-2)

+….+x

^r

+1)) si conclude che x

^m

x

^t

(mod x

^r

-1).

Dunque, dato un polinomio qualunque f(x)=a

0

+a

1

x

+…..+

a

n

x

ⁿ

a coefficienti interi relativi, si ha f(x)  

 n 1 i

i

x

tⁱ

a (mod x

^r

-1)

dove ogni t

i

é il resto della divisione dell’esponente i per r, cioè ogni t

i

coincide con imodr, la riduzione di i modulo r (si devono poi sommare nel secondo membro i termini simili, ossia quelli per cui i resti t

i

sono uguali).

Il polinomio h(x)= 

 n 1 i

i

x

tⁱ

a è di grado <r, ed è l’unico polinomio di grado <r tale che f(x)h(x) (mod x

^r

-1),: infatti se si ha f(x)k(x) (mod x

^r

-1), con k(x) di grado <r, allora h(x)k(x) (mod x

^r

-1), dunque h(x)-k(x) è multiplo di x

^r

-1, ed h(x)-k(x) è il polinomio nullo (altrimenti sarebbe di grado <r e multiplo di x

^r

-1, contraddizione), dunque h(x)=k(x).

Questo unico polinomio h(x) di grado <r tale che h(x)f(x) (mod x

^r

-1) è detto riduzione di f(x) modulo x

^r

-1, ed è indicato con f(x)mod(x

^r

-1): come visto esso si ottiene da f(x) riducendo modulo r tutti gli esponenti dell’indeterminata x.

In particolare, dati i polinomi f(x), g(x) a coefficienti interi relativi, si ha:

f(x)g(x) (mod x

^r

-1)  f(x)mod(x

^r

-1)= g(x)mod(x

^r

-1)

Quindi un algoritmo per verificare se f(x)g(x) (mod x

^r

-1), è quello di verificare se le riduzioni dei

2 polinomi modulo (x

^r

-1)coincidono.

(2)

Esempio: la riduzione modulo x

³

-1 del polinomio f(x)=5+2x+7x

⁵

+11x

⁷

+3x

⁸

si ottiene riducendo tutti gli esponenti modulo 3:

f(x)mod3 = 5+2x+7x

²

+11x+3x

²

= 5+13x+10x

²

Nel test di primalità AKS si sfrutta una “doppia riduzione” modulo m, e modulo x

^r

-1, per un opportuno r, dove m è l’input di cui si deve testare la primalità, nel senso che ora diremo.

Fissati il polinomio x

^r

-1 (con r>1), e un naturale m>1, e dati 2 polinomi a coefficienti interi relativi f(x), g(x), diremo che f(x) è congruo g(x) modulo (x

^r

-1,m) se la differenza f(x)-g(x) è una combinazione lineare di x

^r

-1,m cioé se esistono due polinomi s(x), t(x) a coefficienti interi relativi tale che si abbia f(x)-g(x)=ms(x)+ (x

^r

-1)t(x). In tale caso scriveremo f(x)g(x) (mod x

^r

-1,m).

Anche tale relazione di doppia congruenza è una relazione di equivalenza nell’insieme dei polinomi a coefficienti interi relativi, e che gode delle usuali proprietà: si possono per esempio moltiplicare e sommare congruenze fra polinomi modulo (x

^r

-1,m).

Notiamo che se f(x)g(x) (mod x

^r

-1), allora in particolare f(x)g(x) (mod x

^r

-1,m) , perché se esiste un polinomio t(x) tale che f(x)-g(x)=(x

^r

-1)t(x), allora f(x)-g(x)=ms(x)+ (x

^r

-1)t(x), con s(x)=0.

Analogamente se f(x)g(x) (mod m), allora f(x)g(x) (mod x

^r

-1,m).

Ma in generale se f(x)g(x) (mod x

^r

-1,m) non sempre f(x)g(x) (mod m), e f(x)g(x) (mod x

^r

-1), come vedremo dopo in un esempio.

Dato un polinomio qualunque f(x) a coefficienti interi relativi, se costruiamo la riduzione modulo x

^r

-1 (riducendo gli esponenti modulo r):

g(x)=f(x)mod(x

^r

-1)

e se di g(x) costruiamo la riduzione modulo m (riducendo i coefficienti modulo m):

h(x)=g(x)modm

allora si ha f(x)g(x) (mod x

^r

-1), f(x)-g(x)=s(x)(x

^r

-1), g(x)h(x) (mod m), g(x)-h(x)=mt(x), da cui f(x)-h(x)=s(x)(x

^r

-1)+mt(x), e si conclude che f(x)h(x) (mod x

^r

-1,m).

Questo polinomio h(x) (ottenuto per “doppia” riduzione) ha per costruzione grado <r, e tutti i coefficienti compresi fra 0 e (m-1), ed è l’unico con tale proprietà, come si dimostra con metodi simili ai precedenti: tale polinomio k(x) è detto riduzione di f(x) modulo (x

^r

-1,m), e indicato con f(x)mod(x

^r

-1,m).

Anche in questo caso, un algoritmo per verificare se f(x)g(x) (mod x

^r

-1,m), è quello di verificare se le riduzioni dei 2 polinomi modulo (x

^r

-1,m)coincidono.

Esempio.

Dati m=3, x

⁵

-1, se riduciamo modulo (x

⁵

-1) i polinomi f(x)=1+x

⁵

+5x

⁶

+2x

¹¹

, g(x)=5+2x+2x

⁶

, otteniamo f(x)mod(x

⁵

-1)=2+7x, g(x)mod(x

⁵

-1)=5+4x, e riducendo i risultati modulo 3 otteniamo f(x)mod(x

⁵

-1,3)=2+x=g(x)mod(x

⁵

-1,3), dunque si conclude che f(x)g(x) (mod x

⁵

-1,3).

Notare che però non sono valide le congruenze f(x)g(x) (mod x

⁵

-1), f(x)g(x) (mod 3): la prima non è valida perché f(x)mod(x

⁵

-1)g(x)mod(x

⁵

-1), e la seconda perché per esempio i termini noti di f(x), g(x) non sono congrui modulo 3.

Fissiamo ora un esponente intero positivo k, e costruiamo un algoritmo per calcolare la riduzione della potenza f(x)

^k

modulo (x

^r

-1,m), dove f(x) è un polinomio a coefficienti interi relativi.

Tale algoritmo è la esponenziazione modulare per polinomi, che è molto simile a quella già illustrata per ridurre modulo m una potenza numerica.

Sia t la lunghezza binaria di k, cioé il numero di cifre binarie dell’esponente k:

k=a

t-1

2

^t-1

+ a

t-2

2

^t-2

+….+a

1

2+a

0

(con 0a

i

t-1, con a

t-1

=1)

Costruiamo una successione f

0

(x),f

1

(x),...,f

t

(x) di polinomi a coefficienti interi ponendo:

(3)

f

0

(x)=1; per ogni i>0 f

i

(x)= (f _i _ ₁ ² (x)f(x) ^a

^t^ⁱ

) ^mod(x

^r

^-1,m)

L’ultimo termine f

t

(x) della successione sarà la riduzione f(x)

^k

mod(x

^r

-1,m) cercata (la dimostrazione di tale affermazione si ottiene con ragionamenti simili a quelli utilizzati nel caso dell’esponenziazione modulare numerica).

Dimostreremo ora che, dato in input il numero m, di lunghezza binaria h, l’algoritmo precedente ha complessità di ordine polinomiale rispetto ad h, a patto che siano soddisfatte le seguenti ipotesi:

- l’esponente k è m

- il polinomio f(x) a coefficienti interi relativi è di grado < r e ha tutti i coefficienti compresi fra 0 e (m-1)

- r ha ordine polinomiale O(h

ⁿ

) rispetto ad h

Per calcolare la complessità di tale algoritmo, osserviamo che ogni elemento della successione f

i

(x) con i>0 si calcola dal precedente moltiplicando f

i-1

(x) per sé stesso e per f(x)

^a^t^ⁱ

(quest’ultima potenza uguale ad f(x) oppure ad 1) e riducendo il risultato modulo (x

^r

-1,m).

Poiché f

i-1

(x) è a sua volta una riduzione modulo (x

^r

-1,m), esso è un polinomio di grado <r, e tutti i suoi coefficienti (in numero r) sono compresi fra 0 e (m-1); lo stesso vale per il polinomio f(x).

Per moltiplicare f

i-1

(x) per sé stesso e per f(x)

^a^t^ⁱ

si esegue un numero r

³

di prodotti fra i coefficienti di f

i-1

(x) e di f(x)

^a^t^ⁱ

, e si ottiene un polinomio di grado <r

³

; si deve poi ridurre il risultato modulo x

^r

-1 (quindi ridurre modulo r ognuno degli esponenti, in numero r

³

) ottenendo un polinomio di grado <r, e infine ridurre il risultato modulo m (quindi ridurre modulo m ognuno dei coefficienti, sempre in numero r): tutte queste operazioni hanno complessità di ordine polinomiale rispetto ad h, perché r ha ordine polinomiale rispetto ad h.

Dunque il calcolo di ogni termine della successione f

i

(x) è di complessità polinomiale.

Infine il numero degli elementi della successione è t, numero di cifre binarie dell’esponente k , e quindi (essendo km) non superiore al numero di cifre binarie h di m.