Dati 2 polinomi a coefficienti interi relativi f(x), g(x), il polinomio x

Lezione del 19 maggio 2008

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

-1, per un opportuno r, dove m è l’input, nel senso che ora diremo.

Dati 2 polinomi a coefficienti interi relativi f(x), g(x), il polinomio x

-1 (con r>1), e un naturale m>1, diremo che f(x) è congruo g(x) modulo (x

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

-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

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

-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

-1,m).

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

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

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

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

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

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

-1,m).

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

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

-1), come vedremo dopo in un esempio.

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

-1 (riducendo gli esponenti modulo r):

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

-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

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

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

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

-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

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

-1,m).

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

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

-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)

modulo (x

-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

2

+ a

2

+….+a

2+a

(con 0a

t-1, con a

=1)

Costruiamo una successione f

(x),f

(x),...,f

(x) di polinomi a coefficienti interi ponendo:

f

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

(x)= (f _{i  1} ² (x)f(x) ^a

) ^mod(x

^-1,m)

L’ultimo termine f

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

mod(x

-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

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

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

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

-1,m).

Poiché f

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

-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

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

si esegue un numero r

di prodotti fra i coefficienti di f

(x) e di f(x)

, e si ottiene un polinomio di grado <r

; si deve poi ridurre il risultato modulo x

-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

(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.

Complessivamente l’algoritmo ha complessità polinomiale rispetto ad h.