[PDF] Algorithme du demi-pgcd On considère le calcul

View - Download Algorithme du demi-pgcd

Previous PDF

Next PDF

Algorithme du demi-pgcd

Bruno Grenet

Mars2018

1Introduction : algorithme d"EuclideOn considère le calcul du pgcd de deux polynômesR0etR1à coefficients dans un corps1K,

de degrés respectifsn0etn1 euclidienne deR0parR1et peut donc être ignoré. L"algorithme d"Euclide permet de calculer un2pgcd deR0etR1enO(deg(R0)deg(R1)) opérations dansK.

Euclide(R0,R1):

Entrée : deux polynômes R

0et R1avecdeg(R1)

Sortie : un pgcd de R

0et R1

1.i=0

2.T antque Ri+16=0 :

3.(Qi,Ri+2) DivEucl(Ri,Ri+1)

4.i i+1

5.Renv oyerRi

Soitkla valeur finale dei, de telle sorte queRk+1=0 etRj6=0 pour toutjk.

Définition1.1.

On appelle respectivementsuite des quotientsetsuite des restesde(R0,R1)les suites (Qi)0iOn vérifie aisément que la suite des restes décroit strictement en degré :deg(Ri)>deg(Ri+1)

pour touti. En particulier, pour toutdsupérieur ou égal au degré du pgcd deR0etR1, il existe

un unique indicejtel quedeg(Rj)d>deg(Rj+1). Cette remarque simple est utilisée à de nombreuses reprises dans la suite.

Étant donnée la valeur deQià chaque étape, on peut obtenir la suite des restes grâce au

produit matrice-vecteur (les entrées étant des polynômes) Ri+1 R i+2 =0 1 1Qi Ri R i+1 .1

. On peut définir le pgcd de polynômes à coefficients dans un anneau, mais il faut alors prendre quelques précautions.

Le choix de ne travailler qu"avec des polynômes sur un corps est un choix de simplicité.

2. SiGest un pgcd deR0etR1, alors tout multiple deGpar une constante non nulle deKen est également un.

1 De plus, le pgcd deRi+1etRi+2est égal au pgcd deRietRi+1. On noteTila matrice

0 11Qi

On a alors pour touti R i+2 =TiT1T0R0 R 1

En particulier,

G 0 =Tk1T1T0R0 R 1 oùGest un pgcd deR0etR1. L"objectif de l"algorithme dit du " demi-pgcd » est de fournir un algorithme rapide de calcul de la matriceM=Tk1T0, de laquelle on déduit le pgcd deR0etR1avec deux multiplications

et une addition. On peut également déterminer les coefficients de Bézout sans calcul à partir de

M. En effet, l"égalité précédente montrer queG=M00R0+M01R1, c"est-à-dire que la première

ligne de la matriceMcontient les coefficients de Bézout.

On appelleMlamatrice de pgcd de R0et R1.

2Algorithme du " demi-pgcd »

Dans l"algorithme d"Euclide, la suite des degrés des restes décroît strictement dedeg(R0)

àdeg(G). L"idée générale de l"algorithme du " demi-pgcd » est de factoriser le produitM=

T k1T0 en deux sous-produits, de telle sorte que chaque sous-produit fasse baisser le degré des restes de moitié. Plus exactement, on écrit

M=Tk1Tj+1TjTj1T0

où l"indicejest choisi tel quedeg(Rj)12 deg(R0)>deg(Rj+1). L"utilité de laisser une des matricesTjen dehors de la factorisation apparaîtra claire ultérieurement. On noteD=Tj1T0 etN=Tk1Tj+1de telle sorte queM=NTjD. La matriceMsera alors calculée en calculant en premier lieuN,TjetDpuis en effectuant leur produit.

On remarque que par définition,(TjD)R0R1

=Rj+1 R j+2. Or la correction de l"algorithme d"Euclide repose sur le fait que le pgcd deR0etR1soit le même que le pgcd deRj+1etRj+2. Ainsi, la matriceNest la matrice de pgcd deRj+1etRj+2. On peut donc la calculer par un appel récursif à l"algorithme de calcul de matrice de pgcd. Quant àD, ce n"est pas une matrice de pgcd. Appliquée àR0etR1, elle fournit un couple de restes(Rj,Rj+1)tels quedeg(Rj)12 deg(R0)>deg(Rj+1). On appelle cette matrice lamatrice de demi-pgcd de R0et R1. i L"algorithme du " demi-pgcd » est constitué de deux algorithmes. L"algorithmeMatricePgcd

permet de calculer la matrice de pgcd de deux polyômes, étant donnée leur matrice de demi-pgcd.

L"algorithme DemiPgcdcalcule lui la matrice de demi-pgcd.

2.1L"algorithmeMatricePgcd

On commence par décrire l"algorithmeMatricePgcd, plus simple, qui fait appel à l"algorithme

DemiPgcdqui sera décrit ensuite.

2

MatricePgcd(R0,R1):

Entrée : deux polynômes tels quedeg(R0)>deg(R1).

Sortie : la matrice de pgcd de R

0et R1.

1.D DemiPgcd(R0,R1)

2.Rj R j+1 DR0 R 1

3.Si Rj+1=0, renvoyerD

4.(Qj,Rj+2) DivEucl(Rj,Rj+1)

5.Tj 0 1

1Qj

6.Si Rj+2=0, renvoyerTjD

7.N MatricePgcd(Rj+1,Rj+2)

8.Renv oyerNTjD

Théorème2.1.Soitn=deg(R0), etH(n)la complexité de l"algorithmeDemiPgcd. On suppose que l"algorithmeDemiPgcdest correct, et que sa complexitéH(n)est telle queH(n)/nest croissante et H(n)M(n)oùM(n)est la complexité du produit de deux polynômes de taille n. Alors l"algorithmeMatricePgcdest correct, et son temps de calcul G(n) =O(H(n)).

Démonstration.

La correction de l"algorithmeMatricePgcdest claire d"après celle deDemiPgcd, les étapes3. et6. jouant les rôles decas de base. La complexité de l"étape1. estH(n)par définition. On sait quedeg(Rj)n/2>deg(Rj+1),

donc l"appel récursif à l"étape7. est effectué sur deux polynômes de degré

étape est borné parG(n/2). Les autres étapes, division euclidienne comprise, coûtent un nombre

constant de multiplications de polynômes de degré au plusn. Ainsi,

G(n)G(n/2) +H(n) +cM(n)

pour une certaine constantec. PuisqueH(n)M(n)par hypothèse, on peut réécrireG(n) G(n/2) +c0H(n)oùc0=c+1. On en déduit que pourhG(n)G(n/2h) +c0h1å

j=0H(n/2j). PuisqueH(n)M(n)n, on peut écrireH(n) =na(n)pour une certaine fonctiona(n)1. AlorsåjH(n/2j) =åj(n/2j)a(n/2j)na(n)åj1/2j2H(n), en bornanta(n/2j)para(n). En prenanth=dlog(n)e, on obtientG(n) =O(H(n)). Remarque.Dans l"algorithmeMatricePgcd, on peut obtenir sans calcul supplémentaire le pgcd

lui-même. En effet, à l"étape3. le pgcd estRjet à l"étape6. c"estRj+1. Enfin, si on suppose que

l"étape7. renvoie récursivement non seulement la matriceNmais aussi le pgcdGdeRj+1etRj+2, il suffit de renvoyerGà l"étape8.

Si l"objectif final est d"obtenir le pgcd, le calcul de la matrice de pgcd est inutile. Si aux étapes3.,

6. et8. on renvoie le pgcd au lieu de la matrice de pgcd (et que l"appel récursif calcule donc le pgcd

queRj+1etRj+2), il est clair que l"on obtient encore un algorithme correct, de même complexité

asymptotique. Cette variante permet d"économiser quelques calculs (produits de matrices à l"étape

8. et calcul final du pgcd à partir de la matrice de pgcd).

3 Cependant, on note que la matrice de pgcd permet également de déduire (sans calcul) les

coefficients de Bézout associés aux polynômes d"entrée, ce que ne permet pas la variante évoquée

ci-dessus.

2.2Calcul du demi-pgcd

On s"intéresse maintenant au calcul de la matriceDdu demi-pgcd deR0etR1. Comme pour l"algorithme général, on factorise la matriceDen deux sous-produits. On écrit

D=Tj1Ti+1Ti(Ti1T0)

où l"indiceiest choisi cette fois-ci tel que deg(Ri)34 deg(R0)>deg(Ri+1).

Pour exploiter pleinement l"idée du " diviser pour régner », deux problèmes se posent : d"une

part, les deux matrices de la factorisation ne sont pas des matrices de demi-pgcd, et d"autre part les polynômes auxquels on les applique sont de taille de l"ordre den. On aimerait les calculer comme matrices de demi-pgcd de polynômes de degrés environn/2. Cela est rendu possible par la remarque suivante : siAetBsont deux polynômes de degrés éventuellement grands, mais proches, leur quotient ne dépend que des coefficients de poids fort deAetB. Par exemple, siA=3X100+4X9910X98etB=X992X98+, leur quotient3X+10

de degré1et ne dépend que des deux coefficients dominants deAetB. Ainsi, ce quotient est égal

au quotient dans la division deA?=3X2+4X10parB?=X2. On peut aussi remarquer qu"en appliquant l"algorithme d"Euclide au couple(A,B)ou au couple(A?,B?), le premier reste dans les deux cas a le même coefficient dominant.

Le lemme suivant quantifie ces remarques.ddt

R 0R 1R 2. ..R ?iR iR iFigure 1- Illustration du lemme2.2.

Lemme2.2.

SoitR0de degrén0t+2d(t,d>0) etR1de degrén1avecn0>n1t+d, et R?0=R0quoXtetR?1=R1quoXt. Soit(Ri)iet(R?i)iles suites des restes respectives de(R0,R1)et (R?0,R?1), et j tel quedeg(R?j)d>deg(R?j+1).

Alors pour0ij+1,

R i=R?iXt+R iavec( deg(R?i) =nit et deg(R i)On poseR

i+2=R iR i+1Q?ide telle sorte queRi=Ri+1Q?i+R?i+2Xt+R i+2. Alors puisque deg(R i+1)Ainsi, l"égalitéRi=Ri+1Q?i+ (R?i+2Xt+R i+2)est la division euclidienne deRiparRi+1

puisque le degré du reste est strictement inférieur au degré deRi+1. Par unicité du quotient et

du reste,Qi=Q?i,Ri+2=R?i+2Xt+R i+2etdeg(R i+2)qui signifie que le résultat est démontré jusqu"àRj+1etQj1.On peut déduire le corollaire suivant du lemme2.2.

Corollaire2.3.

SoitAetBdeux polynômes ettetddeux entiers tels qued(deg(A)t)/2e=det deg(A)>deg(B)t. SoitA?=AquoXtetB?=BquoXt, etD?la matrice de demi-pgcd deA?et B?.

Alors D

?AB=Rj R j+1 où(Ri)iest la suite des restes de(A,B)etdeg(Rj)t+d>deg(Rj+1).

Démonstration.

On remarque que la condition sur le degré deAsignifie quedeg(A)est égal àt+2d out+2d1. Le résultat est trivial lorsquedeg(B)deg(R?j+1). De plus, cet indice vérifiedeg(Rj)t+d>deg(Rj+1)d"après le même lemme. Ainsi, la matriceD?est le produitTj1...T0oùTi=0 11Qi. DoncD?AB=Rj R j+1 .2.3L"algorithmeDemiPgcd On peut maintenant décrire un algorithme récursif de calcul de la matrice de demi-pgcd deR0 etR1. 5

DemiPgcd(R0,R1) :

Entrée : deux polynômes tels quedeg(R0)>deg(R1).

Sortie : la matrice de demi-pgcd de R

0et R1.

1.m dn/2e, oùn=deg(R0)

2.Si deg (R1)

3.Renv oyerI2(matrice identité)

4.(R?0,R?1) (R0quoXm,R1quoXm)

5.D?0 DemiPgcd(R?0,R?1)

6.Rj R j+1 D?0 R0R1

7.Si deg (Rj+1)

8.Renv oyerD?09.(Qj,Rj+2) DivEucl(Rj,Rj+1)

T j 0 11Qj

10.Si deg (Rj+2)quotesdbs_dbs46.pdfusesText_46

[PDF] le calcul vectoriel

[PDF] Le calcul vectoriel ( Le produit Scalaire )

[PDF] Le camp d'Auschwitz

[PDF] Le campeur

[PDF] le campeur : Fonction affine par morceaux, valeur absolue, lectures graphiques

[PDF] Le cancer

[PDF] Le cancer de la peau

[PDF] Le cancer et les divisions cellulaire s

[PDF] le cancer nutritionnel

[PDF] Le cancre - Prévert

[PDF] le cancre jacques prévert analyse

[PDF] le Canon

[PDF] Le caoutchouc naturel

[PDF] Le capitaine

[PDF] le capitaine du navire