M1 MATHSTD ALGORITHMIQUE

CHRISTOPHE RITZENTHALER

1. Introduction à la complexité

Exercice 1. On considère la machine de Turing suivante sur l’alphabet 0, a, b (les transi-tions absentes sont considérées comme des états finaux). L’état initial est e

0

et on supposeque le mot commence par un 0.

état lu écrit mouvement nouvel étate0

0 0 D e1

a a D e1

e1

b b D e1

0 0 G e2

a 0 D e3

e2

b 0 D e5

e3

0 a D e4

a a D e4

e4

b b D e4

0 a G e7

e5

0 b D e6

a a D e6

e6

b b D e6

0 b G e7

a a G e7

e7

b b G e7

0 0 G e2

(1) Quelle est la configuration finale sur l’entrée 0ab ?(2) Quelle est la configuration finale sur l’entrée 0baa ?(3) Que fait la machine sur un mot de l’alphabet {a, b} ?

Exercice 2. On considère la génération de toutes les parties d’un ensemble E = {1, . . . , n}.Chaque partie X est représentée par son vecteur caractéristique x avec x[i] = 1 si i 2 Xet 0 sinon. On stocke x en tant que vecteur. La partie vide est donc (0, . . . , 0). Les partiessuivantes sont obtenues en procédant de droite à gauche dans le vecteur courant x. Onremplace tous les 1 par des 0 jusqu’à rencontrer un 0. Celui-ci est remplacé par un 1.C’est l’algorithme d’incrémentation en binaire.

(1) Écrire l’algorithme qui étant donné un vecteur courant x, calcule le vecteur sui-vant.

(2) Quels sont les pires cas ? Calculer leur complexité en termes du nombre de com-paraisons.

(3) Calculer la complexité en moyenne.1

Exercice 3. Montrer que

(1)P

n

i=1

ik = ✓(nk+1

) ;

(2) log n! = ✓(n log n) ;

(3)P

n

i=1

1

i

= ✓(log n).

Exercice 4. Montrer la version 2 du théorème du Maître. On commencera par démontreren utilisant l’écriture en base p que 1

p

d n

p

i e d n

p

i+1 e.

Exercice 5. On considère la suite de Fibonacci

Fn+2

= Fn+1

+ Fn

, F0

= 0, F1

= 1.

(1) Calculer le n-ième terme de la suite.

On considère l’algorithme d’Euclide pour le calcul du pgcd de deux entiers positifs pardivisions successives. Notons n(x, y) le nombre de divisions avec reste effectuées par

Algorithm 1: Procédure gcdinput : x et youtput: pgcd(x, y)if y = 0 then

return xelse

return gcd(y, x mod y)

l’algorithme. Alors n(x, y) = 0 si y = 0 et 1 + n(y, x (mod y)) sinon.

(2) Montrer par récurrence que pour x > y � 0 on a n(x, y) = k implique x � Fk+2

.

(3) En déduire que n(x, y) = O(log x).

Exercice 6. Soit C la fonction vérifiant C(1) = a > 0 et C(n) = C(bn/2c)+C(dn/2e)+bnpour n > 1 et b > 0. Montrer que C(n) = O(n log n).

Exercice 7. Soit à calculer le produit de deux entiers u et v vérifiant 0 u, v < 2

2n

pour un entier n.

(1) Montrer qu’on peut écrire u et v en binaire sur 2n bits.

On pose alors u = 2

nU1

+ U0

et v = 2

nV1

+ V0

avec 0 U0

, V0

, U1

, V1

< 2

n.

(2) Montrer que

uv = (2

2n

+ 2

n

)U1

V1

+ 2

n

(U1

� U0

)(V0

� V1

) + (2

n

+ 1)U0

V0

.

Cette formule (dite de Karatsuba) permet de décomposer le problème de la multiplicationde deux nombres à 2n bits en 3 multiplications de nombres à n bits et quelques additionset décalage. Il est clair que ces dernières opérations demandent un temps linéaire en n.Soit t(n) le temps requis pour multiplier deux nombres à n bits par cette méthode.

(3) Montrer alors que t(2n) = 3t(n)+ c(n) avec t(1) = 1 et en déduire une estimationde la complexité.

Exercice 8. Nous montrons ici que la classe de complexité (polynomiale ou exponentielle)ne dépend pas de la base de représentation de l’entier. Soit g > 1 un entier et a 2 N.

2

On appelle la représentation de a en base g l’unique suite (a1

, . . . , ak

) avec a1

6= 0 etai

2 [0, . . . , g � 1] telle que

a =

kX

i=1

ai

gk�i.

(1) Que vaut k en fonction de a et de g ?On se restreint ici à g = 2 (écriture binaire) et g = 10 (écriture décimale).

(2) Écrire en décimale, 10110.(3) Écrire en binaire 105 en utilisant l’algorithme de division euclidienne.(4) Quelles sont les complexités de ces opérations en supposant que l’addition (resp.

la multiplication, resp. la division euclidienne) de deux éléments a � b a un coupen O(log(a)) (resp. O(log(a)2), resp. (resp. O(log(a)2)).

(5) Conclure.

3

2. Tri

Exercice 9. Exécuter le tri par sélection sur la liste A = [5, 2, 4, 6, 1, 3]. Écrire le pseudo-code correspondant à cet algorithme.

Exercice 10. Le but de cet exercice est de montrer qu’un algorithme de tri par compa-raisons et échanges a pour complexité dans le pire cas au mieux O(n log n), où n désignela longueur du tableau à trier.

(1) De combien de manières peut-on permuter les éléments d’un tableau [a1

, a2

, . . . , an

] ?(2) Supposons que l’on applique un algorithme de tri donné à [a

1

, a2

, . . . , an

]. Pourchaque comparaison effectuée au cours de l’algorithme, il y a deux possibilités :soit on change les éléments comparés, soit on ne les change pas.

Supposons que, au maximum, l’algorithme s’exécute en C(n) comparaisons(C(n) est donc la complexité dans le pire cas). Montrer que 2C(n) > n! en représen-tant l’algorithme par un arbre de décision. On s’inspirera de l’exemple ci-dessouspour le tri par insertion sur une liste à 3 éléments.

(3) Montrer qu’alors asymptotiquement, la complexité dans le pire cas est supérieureà un O(n log n).

Exercice 11. Montrer que la complexité exacte du tri fusion est ndlog2

ne� 2

dlog2 ne+1.

Exercice 12 (tri par tas). Étant donné un tableau, on peut le représenter sous formed’un arbre binaire de la façon suivante. On place le premier élément à la racine de l’arbre,puis les deux éléments suivants sur les deux fils de la racine, puis les 4 éléments suivantssur les 4 petits-fils, etc. Si la taille du tableau n’est pas de la forme 2

k � 1, on remplitla dernière ligne de l’arbre en commençant par la gauche. Ainsi, par exemple, le tableau[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] sera-t-il représenté comme suit :

(1) Si on numérote les éléments d’un tableau à partir de 0, quels sont les numéros desfils de l’élément numéro i ?

4

On appelle tas un tableau représenté comme ci-dessus sous forme d’un arbre bi-naire, et tel que chaque noeud est plus grand que ses deux fils. Par exemple, le tableau[10, 9, 6, 7, 8, 2, 5, 1, 4, 3] est un tas, comme on peut le vérifier sur sa représentation sousforme d’arbre :

Le tri par tas est un algorithme de tri qui utilise la structure de tas. Un des avantages decet algorithme est qu’on peut le programmer en place, c’est-à-dire qu’il n’utilise pas plusde place mémoire que celle nécessaire pour stocker le tableau à trier. Un autre avantageest qu’il permet de faire un tri dynamique, c’est-à-dire que l’on peut ajouter au cours del’algorithme de nouveaux éléments à trier.

On se donne un tableau d’entiers de taille n. Celui-ci sera modifié directement au coursde l’algorithme. On considèrera un tas qui sera constitué des k premiers éléments dutableau, k pouvant varier entre 1 et n.

La première étape consiste, étant donné un tableau quelconque, à le transformer entas. Pour cela, on construit le tas progressivement, en y ajoutant les éléments un à un(k variera de 1 à n), et en les « remontant » progressivement s’ils sont mal placés : sil’élément que l’on vient d’ajouter est plus grand que son père, on l’échange avec celui-ci,et ainsi de suite.

(1) Montrer que si A est un tas, et qu’on ajoute à A un élément à la dernière placelibre, alors, l’arbre obtenu en changent cet élément génération par génération avecses ancêtres plus petits que lui est à nouveau un tas.

(2) Montrer que si un tableau est un tas, alors son premier élément est aussi sonélément maximal.

Une fois que l’on a transformé notre tableau en tas, la procédure est la suivante : changele premier et le dernier élément du tas, et on diminue k de 1 (ainsi, l’élément qui étaiten tête et que l’on vient de placer à la fin du tas n’en fait plus partie : on n’y toucheplus jusqu’à la fin de l’algorithme). Les k premiers éléments du tableau ainsi obtenu neforment en général plus un tas : l’élément que l’on vient de déplacer de la dernière à lapremière position est en général mal placé. On « descend » alors celui-ci en l’échangeantavec celui de ses fils qui est le plus grand, et ainsi de suite, jusqu’à ce que ses deux filssoient plus petits que lui. On recommence cette étape jusqu’à ce que k soit égal à 1

(1) Soit A un tas. Montrer que si on retire son premier élément et qu’on le remplacepar le dernier, puis que l’on descend comme explicité ci-dessus, alors l’arbre obtenuest à nouveau un tas.

(2) Montrer qu’à la fin de cette procédure, le tableau est trié.

(3) Déterminer la complexité de l’algorithme dans le pire cas.

Remarque : on a présenté ici une version de l’algorithme utilisant des arbres binaires. Onpeut écrire sur le même principe un algorithme utilisant des arbres m-aires, et ce pourtout entier m > 2. Le plus efficace est celui utilisant des arbres ternaires (m = 3).

5

3. Graphes

Exercice 13. On considère le graphe orienté donné par la matrice d’adjacence suivante2

66666664

0 1 0 0 0 1 0

0 0 1 1 0 0 0

0 0 0 0 0 0 0

0 0 0 0 1 0 0

0 0 0 0 0 0 1

0 1 0 0 1 0 1

0 0 1 0 0 0 0

3

77777775

Dessiner le graphe. Montrer qu’il est sans circuit en donnant une liste topologique de sessommets.

Exercice 14. Montrer que pour tout i, j, k 2 S on a (i, k) 2 Ak

si et seulement si(i, k) 2 A

k�1

. De même (k, j) 2 Ak

si et seulement si (k, j) 2 Ak�1

.

Exercice 15. On considère le graphe orienté donné par la matrice d’adjacence suivante2

66664

0 1 0 0 0

0 0 1 0 0

1 0 0 1 1

0 0 0 0 1

0 0 0 1 0

3

77775

Donner la matrice de la relation d’accessibilité.On munit alors ce graphe des valeurs suivantes :

(1, 2) (2, 3) (3, 1) (3, 4) (3, 5) (4, 5) (5, 4)1 2 -3 2 1 -4 3

Calculer les valeurs maximales des chemins entre deux sommets.

Exercice 16. Montrer qu’un arbre binaire complet à p � 1 sommets externes possèdep� 1 sommets internes.

Exercice 17. Montrer que dans un graphe non orienté avec au moins deux sommets,il existe deux sommets qui ont le même degré, i.e. même nombre d’arêtes. En déduireque dans un groupe de personnes, deux personnes ont toujours le même nombre d’amisprésents.

Exercice 18. Montrer qu’un graphe non-orienté dont tous les sommets ont des degréssupérieurs ou égaux à 2 a un cycle.

Exercice 19. Effectuer un parcours en largeur et en profondeur du graphe non orientédonné par la liste des voisins (i.e. le voisin de 1 est {11}, les voisins de 2 sont {4, 6, 8, 10, 12},. . . ).({11}, {4, 6, 8, 10, 12}, {6, 9, 12}, {2, 8, 12}, {10}, {2, 3, 12}, {}, {2, 4}, {3}, {2, 5}, {1}, {2, 3, 4, 6}).Donner des forêts couvrantes dans chaque cas.Effectuer un parcours en profondeur du graphe orienté de l’exercice 13.

6

4. Graphes (suite)

Exercice 20. Calculer les composantes fortement connexes du graphe ci-dessous en uti-lisant successivement les trois algorithmes du cours et en commençant au sommet v.

Exercice 21. Calculer un arbre couvrant minimal et les plus courts chemins pour legraphe valué suivant à partir d’un des sommets de votre choix (la valuation manquanteest 5 et dans le cas des plus courts chemins, on changera le �3 en 3).

Exercice 22. Soit G, c un graphe valué connexe. Montrer que si la valuation est constantealors un arbre des plus courts chemins entre deux sommets quelconque est un arbrecouvrant minimal. Montrer que la réciproque n’est pas vraie et donner un exemple degraphe valué pour lequel un arbre des plus courts chemins n’est pas un arbre couvrantminimal.

Exercice 23. Montrer le théorème des parenthèses : dans un parcours en profondeurd’un graphe G pour deux sommets u, v, une et une seule des trois conditions suivantesest vérifiée :

(1) Les intervalles [d(u), f(u)] et [d(v), f(v)] sont disjoints et ni u ni v n’est un des-cendant de l’autre dans la forêt de parcours.

(2) L’intervalle [d(u), f(u)] est entièrement inclus dans l’intervalle [d(v), f(v)] et u estun descendant de v dans un arbre de parcours.

(3) L’intervalle [d(v), f(v)] est entièrement inclus dans l’intervalle [d(u), f(u)] et v estun descendant de u dans un arbre de parcours.

7

Puis on démontrera le théorème du chemin blanc : v est un descendant de u dans la forêtd’un parcours en profondeur si et seulement si, au moment d(u), il existe un chemin deu à v composé uniquement de sommets blancs.

Exercice 24. On considère une matrice carrée P extraite de la matrice d’incidence �.(1) Combien P a-t-elle au maximum de coefficient non nul sur chacune de ses co-

lonnes ?(2) Si P a un 1 et un �1 sur chacune de ses colonnes montrer que det(P ) = 0.(3) Par récurrence et développement du déterminant selon une colonne bien choisie,

montrer que detP = 0, 1 ou �1.(4) Que représentent les coefficients de la matrice �

t

� ?On s’intéresse maintenant à la matrice d’adjacence M . Soit n le nombre de sommets deG.

(5) Montrer que pour tout 1 k n, le coefficient (i,j), noté mk

ij

, de la matrice Mk

est égal au nombre de chemins de longueur k du sommet i au sommet j.(6) Soit A = Id+M +M2

+ . . .+Mn�1. Donner une condition nécessaire et suffisantepour qu’un coefficient de A ne soit pas nul.

8

5. Polynômes : multiplications

Exercice 25. Montrer que, pour multiplier deux polynômes de degrés m et n, l’algo-rithme naïf demande au plus (m + 1) · (n + 1) multiplications dans A et mn additionsdans A.Estimer la complexité binaire de l’algorithme naïf lorsque les polynômes ont degré n etdes coefficients entiers bornés en valeur absolue par un entier H.Shigeru Kondo a calculé 25000000000 décimales de ⇡ sur un PC de bureau en 2003. Cetype de calcul repose sur la multiplication d’entiers. En supposant que la machine deKondo était capable d’effectuer 1012 opérations à la seconde, montrer que Kondo n’a pasutilisé l’algorithme naïf.

Exercice 26. On explique ici sur un exemple la méthode dite de Toom-Cook d’ordre kpour faire le produit de deux entiers. On prendra dans l’exemple k = 3 et on cherche àmultiplier m et n avec

m = 1234567890123456789012, n = 98765432198765432109.

(1) Trouver une base B = 10

i telle que dans cette base le nombre de chiffres de m etn soit au plus k. On note m

i

et ni

les chiffres de m et n en base B.On forme alors les polynômes p(x) = m

2

x2

+m1

x+m0

et q(x) = n2

x2

+ n1

x+ n0

.(2) Montrer que le coût du calcul de mn (en base 10) est comparable au coût du

calcul de pq.(3) En évaluant p et q en 0, 1,�1,�2 et 1 (ce qui revient à prendre le coefficient

du terme dominant), montrer qu’on peut obtenir le produit pq par évaluation etinterpolation sur des entiers de taille k fois plus petite.

(4) En déduire un algorithme récursif et sa complexité.

Exercice 27. Dans cet exercice, on se place dans le corps F17

. On choisit deux polynômesde F

17

[x] :f(x) = 5x3

+ 3x2 � 4x+ 3, g(x) = 2x3 � 5x2

+ 7x� 2.

On cherche à calculer le produit h = fg à l’aide de la transformée de Fourier rapide.Puisque le polynôme produit h sera de degré 6, on choisit la puissance de 2 supérieure laplus proche, c’est à dire 2

3

= 8. Ainsi n = 8 pour la suite de l’exercice.(1) Trouver une racine ! primitive 8-ème de l’unité dans F

17

(possible car 8|16 =

17� 1). On montrera que t 2 F17

est un candidat si et seulement si t est un carréet t4 6= 1.

(2) Calculer, à l’aide de la FFT, la transformée de Fourier en ! des polynômes f et g.À chaque étape, on ne développera qu’une branche sur les deux de l’arbre binairerécursif.

On se donne maintenant les valeurs de fg en w0, . . . , w7 : 14, 15, 0, 0, 5, 13, 5, 2.(3) Calculer !�1 dans F

17

.(4) Calculer, à l’aide de FFT, le coefficient constant et le coefficient en x4 du polynôme

produit h, résultats de la transformée de Fourier inverse utilisant !�1.(5) Comparer avec le résultat obtenu en faisant le produit “à la main”.

9

6. Polynômes : inversion, division euclidienne, interpolation

Exercice 28. Étant données deux séries formelles F,G on définit d(F,G) = 2

�val(F�G)

où val est l’indice du premier terme non-nul d’une série (1 si la série est nul). Montrerqu’il s’agit d’une distance.

Exercice 29. On choisit deux polynômes de Q[x] : a = 5x5

+ 4x4

+ 3x3

+ 2x2

+ x etb = x2

+ 2x + 3. Effectuer de manière efficace la division euclidienne de a par b (on nefera tout de même pas les multiplications par la FFT).

Exercice 30. Soit A un anneau commutatif. On note A(X) l’anneau des fractions ra-tionnelles sur A. Ses éléments sont de la forme A/B avec A,B 2 A[X] et B 6= 0. Ondéfinit le degré de cette fraction comme max(deg(A), deg(B)). On souhaite calculer ledéveloppement en série formelle F lorsque B(0) est inversible.

(1) Montrer que deux fractions rationnelles de degré au plus n peuvent être addition-nées et multipliées en temps O(M(n)).

(2) Montrer qu’une fraction rationnelle est uniquement déterminée par les deg(A) +deg(B) + 1 premiers termes de son développement.

(3) Montrer qu’on peut calculer le développement à l’ordre N d’une fraction ration-nelle de degré d N en O(M(N)) opérations.

(4) Montrer qu’on peut se ramener au cas où d = deg(B) en O(M(d)) opérations.On souhaite aboutir à une meilleure complexité et montrer le résultat suivant

Théorème 6.1. Soit A/B de degré au plus d avec B(0) inversible. Le développement en

série formelle de A/B à précision N � d peut se calculer en O(NM(d)/d) opérations.

Pour montrer le théorème on aura besoin du lemme suivant.

Lemme 6.2. Soit A/B avec B(0) inversible. Soit d le degré de B, deg(A) < d et � 0. Les

coefficients c

, . . . , c+d�1

du développement de A/B sont les coefficients de X2d�2, . . . , Xd, Xd�1

du produit

(X

(mod B(1/X)Xd

))(c2d�2

+ . . .+ c0

X2d�2

).

On commence par montrer le lemme. Soit C la matrice de la multiplication par X dansla base 1, X, . . . , Xd�1 de B = A[X]/( ¯B) où ¯B = B(1/X)Xd.

(5) Montrer qu’on a (cn+1

, . . . , cn+d

) = (cn

, . . . , cn+d�1

) · C pour tout n � 0 (onexploitera l’égalité B · F = A et le fait que deg(A) < d).

(6) En déduire un algorithme en O(dN + M(d)) pour calculer le développement àl’ordre N .

(7) En déduire que c+n

peut être obtenu à partir de (cn

, . . . , cd+n�1

) et de C.(8) En utilisant l’interprétation de C comme multiplication par X, montrer que la

première colonne de C contient les coefficients du polynôme X

(mod

¯B).(9) En déduire le lemme.

(10) Montrer qu’en utilisant dN/de�2 fois le lemme avec = 2d, . . . , on peut calculerc2d

, . . . , cN

.(11) Montrer qu’on peut calculer les restes Xdi

(mod

¯B) pour 0 i dN/de enO(N/d) opérations dans B.

(12) Montrer qu’on peut calculer c0

, . . . , c2d�2

en O(M(d)) opérations dans A.(13) Conclure.

10

7. Algorithme d’Euclide

Exercice 31. On considère l’algorithme d’Euclide étendu avec deg(a) � deg(b)

R0 = a ; R1 = b ;U0 = 1 ; U1 = 0 ; V 0 = 0 ; V 1 = 1 ;while R

i

> 0 :Q

i

= DivisionQuotient(Ri�2

, Ri�1

) ;R

i

= DivisionRemainder(Ri�2

, Ri�1

) ;Ui

= Ui�2

�Qi

Ui�1

;Vi

= Vi�2

�Qi

Vi�1

;return R

i�1

;

Soit i0

tel que Ri0+1

= 0. Montrer qu’on a

Ui0a+ V

i0b = pgcd(a, b).

On souhaite estimer la complexité de cet algorithme. Quand le degré de a est granddevant le degré de b, les degrés de V

i

peuvent devenir très grands. On ne calculera doncpas les V

i

et on retrouvera Vi0 à la fin grâce à la relation ci-dessus.

(1) Montrer que i0

deg b+ 1.

(2) Montrer que degQi

= degRi�2

� degRi�1

et que pour tout i i0

on a degUi

deg b� degR

i�1

. En déduire une majoration du coût du calcul de Ui

(en utilisantl’algorithme naïf pour le produit).

(3) En déduire que le coût total de l’algorithme est majoré par O(deg a deg b) (enutilisant l’algorithme naïf en O(n(m� n)) pour la division euclidienne).

(4) Montrer qu’on a bien degUi0 deg b et deg V

i0 deg a.

Exercice 32. (1) Calculer le pgcd et les coefficients de Bézout pour 252 et 90 enutilisant Euclide étendu.

(2) Déterminer une solution particulière dans Z2 de l’équation (E) : 252x+90y = 36.

(3) Trouver toutes les solutions dans Z2 de l’équation (E).

Exercice 33. Soient m et n deux entiers premiers entre eux. Le théorème des resteschinois traduit l’isomorphisme d’anneaux � : Z/mnZ ! Z/mZ⇥Z/nZ qui à a (mod mn)associe (a (mod m), a (mod n)). Donner une formule pour l’application réciproque etappliquer cela à la résolution du système x ⌘ 3 (mod 7), x ⌘ 4 (mod 11).

8. Matrices et algèbre linéaire

Exercice 34. Trouver une décomposition LU de la matrice

2

44 �5 6

8 �6 7

12 �7 12

3

5.

Exercice 35. Résoudre l’équation2

41 5 4

2 10 3

5 8 5

3

5

2

4x1

x2

x3

3

5=

2

412

9

5

3

5

à l’aide d’une décomposition LUP.11

Exercice 36. Montrer que la complexité Mm(n) de la multiplication de deux matricesde taille n est un O(S(n)) où S(n) est la complexité de l’élévation au carré d’une matricede taille n.

Exercice 37. (1) Montrer qu’il est possible d’effectuer le produita �bb a

� xy

�

en 3 multiplications scalaires.(2) En déduire que deux nombres complexes peuvent être multipliés en utilisant 3

multiplications réelles.(3) Montrer qu’on peut calculer le quotient de deux nombres complexes en utilisant

au plus 7 multiplications et divisions réelles.(4) Donner un algorithme qui utilise seulement 6 opérations de ce type.

Exercice 38. Le but de cette exercice est de démontrer que le calcul de l’inverse d’unematrice n’est pas plus difficile que le calcul du déterminant à l’aide des techniques de dé-rivation automatique. Pour cela on formalise ce qu’on entend ici par programme. Il prendune suite d’indéterminées Y

1

, . . . , Ym

sur un corps K et une suite d’instruction g1

, . . . , gL

où gi

est un polynôme Gi

de la forme ai

opi

a0i

où ai

, a0i

sont dans K [ {G1

, . . . , Gi�1

} [{Y

1

, . . . , Ym

} et opi

est dans {+,�⇥}. La taille du programme est L. On dit que le pro-gramme calcule F si F 2 {G

1

, . . . , GL

}. Par exemple le programme qui prend en entréesY1

, Y2

, Y3

, Y4

avec

G1

= Y1

⇥ Y4

G2

= Y2

⇥ Y3

G3

= G1

�G2

calcule le déterminant de la matriceY1

Y2

Y3

Y4

�et il est de taille 3.

Si G 2 K[Y1

, . . . , Ym

], on appelle gradient de G l’ensemble de ses m dérivées partielles.(1) Soient G,H 2 K[Y

1

, . . . , Ym

]. Exprimer les dérivées partielles de G+H, de G�Het de GH en fonctions de G,H et des dérivées partielles de G et de H. En déduirequ’étant donné un programme de taille L qui calcule G on peut en déduire unprogramme de taille O(Lm) qui calcule G et son gradient.

(2) Soient G 2 K[Y1

, . . . , Ym

] et H 2 K[Y1

, . . . , Ym+1

] tels que

G = H(Y1

, . . . , Ym

, Yi

⇥ Yj

).

Exprimer les dérivées partielles de G en fonction de H et de ses dérivées partielles.Traiter ensuite les cas où ⇥ est remplacé par ±.

(3) Soient G 2 K[Y1

, . . . , Ym

] et H 2 K[Y1

, . . . , Ym+1

] tels que

G = H(Y1

, . . . , Ym

, Yi

opYj

).

On suppose connu un programme de taille L pour calculer H et son gradient.Montrer qu’on peut en déduire un programme de taille L+O(1) qui calcule G etson gradient.

(4) En déduire par récurrence que si G 2 K[Y1

, . . . , Ym

] peut être calculé par un pro-gramme de taille L alors G et son gradient peuvent être calculés par un programmede taille O(L) (le O ne dépendant pas de m).

12

(5) Soient X1,1

, . . . , Xn,n

, n2 indéterminées et D le déterminant de la matrice

M =

2

4X

1,1

. . . X1,n

......

Xn,1

. . . Xn,n

3

5 .

Montrer que le gradient de D permet de retrouver les entrées de la comatrice Nde M .

(6) Montrer que si on a un programme de taille L qui calcule D alors on a un pro-gramme de taille O(L) qui calcule l’inverse de M . Conclure.

13

9. Résultant

Exercice 39. Soit P = Xp

+ a1

Xp�1

+ . . .+ ap

un polynôme unitaire à coefficients dansun corps K. Montrer que

(�1)

p(p�1)/2ResX

(P, P 0) = Discr(P ) =

Y

1i<jp

(↵i

� ↵j

)

2

où les ↵i

sont les racines de P .Soit P un polynôme unitaire à coefficients réels, de degré p. Montrer que si Discr(P ) > 0,alors le nombre de racines réelles de P est congru à p modulo 4, et que si Discr(P ) < 0,alors le nombre de racines réelles de P est congru à p� 2 modulo 4. On remarquera quece sont les facteurs (↵� ↵) pour ↵ 2 C \ R qui sont les facteurs déterminants.Si P = X3

+ aX + b, discuter son nombre de racines réelles.

10. Polynôme : irréductibilité et factorisation

Exercice 40. On propose le test suivant d’irréductibilité d’un polynôme sur un corpsfini

Algorithm 2: Test d’irréductibilité de Rabininput : un polynôme f 2 F

q

[x] unitaire de degré n et p1

, . . . , pk

les diviseurspremiers de n

output: Irréductible ?for j = 1 ! k do

nj

= n/pj

for i = 1 ! k dog = gcd(f, xq

ni � x (mod f)) if g 6= 1 then“f est réductible” : break

g = xq

n � x (mod f) if g = 0 then“f est irréductible”

else“f est réductible”

(1) Montrer que l’algorithme est correct.

(2) Montrer que le calcul des xq

ni(mod f) se fait en O(nM(n) log(n) log(q)) opéra-

tions.

(3) Comment peut-on adapter l’algorithme si on ne connaît pas la factorisation de n ?

Exercice 41. On cherche à factoriser les polynômes du second degré sur un corps finiFq

= Fp

n avec p 6= 2.

(1) on peut se ramener à X2 � a.

(2) On suppose a non nul. Montrer qu’alors ce polynôme a une racine dans le corpssi et seulement si a(q�1)/2

= 1.

(3) Montrer que si c’est le cas et que si q ⌘ 3 (mod 4), on peut calculer une racinecarrée de a par a(q+1)/4.

(4) En déduire la complexité du calcul dans ce cas.14

Algorithm 3: Algorithme de Shanksinput : a,b, t,soutput: Racine carrée de aB = at ; X = a(t+1)/2 ; z = bt ; Y = z ;R = s� 1

while R � 1 doif B2

R�1= 1 then

Y = Y 2 ;else

B = BY 2 ;X = XY ;Y = Y 2 ;

R = R� 1 ;return X

(5) Si maintenant q ⌘ 1 (mod 4), on écrit q � 1 = 2

st avec t impair et s � 2. Onsuppose connu b 2 F

q

qui n’est pas un carré. On considère l’algorithme ci-dessous.Pour vérifier que l’algorithme renvoie bien une racine carrée de a, on démontrerapar récurrence que les relations suivantes sont satisfaites.

8>>><

>>>:

aB = X2

Y 2

R ⌘ �1 (mod p)

B2

R ⌘ 1 (mod p)

R � 0

Exercice 42. (1) Montrer que si f, g 2 Q[X] sont unitaires tels que fg 2 Z[X] alorsf, g 2 Z[X] (on considèrera le plus petit a, b 2 N tel que af, bg 2 Z[X] et, si ab 6= 1

on considère un premier p qui divise ab. On montrera alors que (a/p)f 2 Z[X],contradiction). En déduire qu’un polynôme de Z[X] unitaire est irréductible surZ si et seulement si il est irréductible sur Q.

(2) Montrer que le polynôme X5

+ 4 est irréductible sur Z.(3) Le polynôme 7X3 � 5X2 � 9X + 4 a-t-il des racines rationnelles ?(4) Démontrer que X4

+X + 1 et X6

+X2

+ 1 sont irréductibles sur Z.(5) Soient a

1

, . . . , an

2 Z distincts et n � 2. Montrer que le polynôme

(X � a1

) · · · (X � an

)� 1

est irréductible sur Z.(6) Démontrer que 1 + (X � 1)

2

(X � 3)

2 est irréductible dans Q[X].

Exercice 43. Soit p un nombre premier et n > 1 un entier. On pose P (X) = Xn

+X+p.(1) Montrer que toute racine z de P dans C vérifie |z| � 1. Quand a-t-on égalité ?(2) On suppose p 6= 2 ou n pair. Montrer que P est irréductible sur Q.(3) On suppose p = 2 et n impair. Montrer que P (X) = (X + 1)Q(X) avec Q

irréductible sur Q.

11. Primalité

Exercice 44. Soit n un entier pseudo-premier en base 2, c.-à-d. tel que n n’est paspremier mais 2n�1 ⌘ 1 (mod n). On va montrer qu’il existe une infinité de tels nombres.

15

(1) Montrer que 2

n � 1 est pseudo-premier en base 2. On pourra utiliser le fait quepour tous entiers a, n, an � 1 est divisible par a� 1.

(2) Conclure.

Exercice 45. On rappelle qu’un témoin de non-primalité d’un entier n impair pourle test de Miller-Rabin est un entier a premier à n tel que, si on écrit n � 1 = 2

sd avecd impair, alors ad 6⌘ 1 (mod n) et quelque soit r 2 {0, . . . , s�1} on a a2

rd 6⌘ �1 (mod n).

Montrer que s’il existe un entier a témoin de non-primalité pour n tel que an�1 ⌘ 1

(mod n) alors on peut trouver un facteur de n (On pourra commencer par montrer qu’ilexiste r 2 {0, . . . , s� 1} tel que a2

rd 6⌘ 1 (mod n) et (a2

rd

)

2 ⌘ 1 (mod n)).

Exercice 46. Montrer que p est premier si et seulement si (p�1)! ⌘ �1 (mod p). Quelleest la complexité du test de primalité sous-jacent ?

Exercice 47. Soit p et q deux grands nombres premiers disctincts (dans la réalité aumoins 1024 bits chacun). Posons n = pq. Choisir ensuite un couple (e, d) tel que ed ⌘ 1

(mod �(n)). Ce couple sert à faire de la cryptographie à clé publique (ici c’est le systèmeRSA) :

(1) Alice publie la clé e et le module n.(2) Si Bob souhaite envoyer à Alice un message m 2 [1, . . . ,m� 1], il envoie y = me

(mod n).(3) Alice décode le message en calculant m = md

(mod n).On peut montrer que trouver la clé secrète d est aussi difficile que factoriser n.Montrer que le protocole fonctionne puis donner la complexité des différentes opérations.

16