Complexité d’algorithmes

En algorithmique, il faut pouvoir mesurer la taille d’un objet et le nombre d’opérations élémentaires effectuées par un algorithme.

Ces notions se déclinent à plusieurs niveaux de granularité :

  • taille en nombre de bits, d’octets, en nombre de coefficients dans un anneau \(A\), en degré de polynôme...
  • complexité en nombre d’opérations sur un bit, en nombre d’additions ou de multiplications sur des entiers, en nombre d’opérations \(+,\times\) sur un anneau fixé...

On utilise les notations \(O(\;)\) pour estimer seulement le terme dominant de ces mesures.

Taille

  • Un entier \(N\) se représente en base \(b\) au moyen de \(n+1\) chiffres \(d_0,\dots d_n\in\set{0,b-1}\), où \(n=\floor{\log_b(N)}\).

    On dit qu’un entier inférieur à \(b^n\) est de taille \(O(n)\) (et le \(O\) ne dépend pas de la base).

  • Un polynôme de degré \(n\) se représente par \(n+1\) coefficients (ou par \(n\) évaluations et un coefficient dominant)

  • Un élément d’un corps fini \(\F_{p^n}\) se représente par une classe de \(\F_p[x]/(P)\), où \(P\in\F_p[x]\) est irréductible de degré \(n\), soit \(n\) entiers inférieurs à \(p\).

    La taille est donc \(O(n\log p)\).

  • Un ordinateur ne peut pas représenter un nombre réel. À la place, on travaille à précision fixée avec des approximations flottantes \(1,e_1e_2\dots e_n \times 2^e\), avec une mantisse de \(n\) bits et un exposant \(e\) entier.

    Attention, ce ne sont que des approximations de nombres réels, on a des problèmes d’erreurs d’arrondi qui se propagent quand on travaille avec.

  • Un élément d’un espace vectoriel de dimension \(n\) se représente par \(n\) coefficients (ex: polynômes, matrices, etc.)

  • Une matrice de \(M_n(A)\) se représente avec \(n^2\) coefficients de \(A\) : c’est la version pleine. Alternativement, si beaucoup de coefficients sont nuls, on peut la représenter de manière beaucoup plus économique par une liste de triplets (ligne, colonne, coefficient). C’est la version dite creuse.

    Idem avec les polynômes, surtout en plusieurs variables.

Addition et multiplication

Sans parallélisme, la complexité minimale de tout algorithme sur un entier de taille \(n\) est \(n\). Le seul fait de stocker ou de lire l’entier prend ce temps. Une opération élémentaire quand on travaille sur les entiers est une modification d’un bit (un processeur travaille par paquets de 32 ou 64 bits).

Un processeur fait de l’ordre d’un milliard d’opérations (additions, multiplications) sur des blocs de 32 ou 64 bits par seconde.

Remarque

cependant, tester la parité de \(n\) revient à n’en lire que le dernier bit, c’est assez indépendant de la taille de \(n\).

Soit \(P(x)\in A[x]\) un polynôme de degré \(n\) à coefficients dans un anneau \(A\). Une opération élémentaire relativement à \(A[X]\) est une opération \(+,-,\times\) de \(A\).

addition

complexité de l’addition de deux entiers de \(n\) chiffres (resp. de deux polynômes de \(A[x]\) degré \(n\)) en nombre d’opérations entre deux chiffres (resp. d’additions de \(A\))

  • méthode de primaire \(O(n)\)

multiplication

complexité de la multiplication de deux entiers de \(n\) chiffres (resp. de deux polynômes de degré \(n\))

  • algorithme naïf \(O(n^2)\)
  • décomposition de Karatsuba \(O(n^{1.58})\)
  • algorithme de Shönhage-Strassen (FFT) \(O(n\log(n)\log\log(n)^2)\)

Une fois qu’on sait additionner et multiplier les entiers, on sait aussi

  • prendre des puissances (exponentiation), voir tp.

    Il suffit de \(O(\log n)\) multiplications pour prendre une puissance \(n\).

  • diviser (algorithme de primaire ou voir tp)

  • calculer dans \(\Q\), dans \(\Z/n\Z\), dans \(\R\)

  • additionner et multiplier les matrices, les polynômes, les séries

  • calculer des pgcd, des relations de Bézout (voir tp Euclide)

  • calculer dans des quotients, des corps finis (voir tp corps finis)

Algèbre linéaire

multiplication dans \(M_n(K)\)

en termes d’opérations élémentaires de \(K\) (surtout multiplication)

  • algorithme naïf \(O(n^3)\)
  • décomposition de Strassen \(O(n^{2.81})\)

Proposition

  • déterminant, inversion \(O(n^3)\) (par pivot de Gauss)
  • polynôme caractéristique \(O(n^4)\) (méthode de Le Verrier ou Faddeev)
  • calculs d’image, de noyau, résolution de systèmes linéaires : tout est polynomial, avec des exposants raisonnables.

Note

un principe

Si on sait ramener un problème à un problème d’algèbre linéaire, on a «gagné».

Factorisation (d’entiers)

Alors que la multiplication d’entiers se décompose bien selon les chiffres, rien de tel pour la factorisation (en dehors des règles de 3 liées à la base 10). On ne sait pas retrouver les facteurs d’un produit, les meilleures techniques sont complètement exponentielles en le nombre de chiffres.

Définition

Soit \(N\) un entier de \(n=O(\log N)\) chiffres.

On pose \(L_N(a,c) = \exp(cn^a (\log n)^{1-a})\)

  • \(L_n(0,c) = n^c = \log(N)^c\), complexité polynomiale d’exposant \(c\)
  • \(L_n(1,c) = e^{cn} = N^c\), complexité exponentielle de facteur \(c\)

Proposition

pour factoriser un entier \(N\) de \(n\) chiffres dont le plus petit facteur premier est \(p\leq\sqrt N\).

  • divisions \(O(p)=O(\sqrt N)=O(2^{\frac{n}2})\) soit \(L_N(1,\frac12)\)
  • méthode Rho de Pollard \(O(\sqrt p)\) soit \(L_N(1,\frac14)\)
  • crible quadratique \(O(e^{c\sqrt{\log N\log\log N}})\) soit \(L_N(\frac12,c)\)
  • crible algébrique \(L_N(\frac13,c)\).

Le deux dernières méthodes consistent à se ramener à de l’algèbre linéaire en construisant des matrices de relations. C’est l’obtention de ces matrices qui est la phase la plus délicate.

Note

un autre principe

Le fait qu’on ne sache pas factoriser les nombres (en dehors des petits) est à la base de la cryptographie.

  • moins de 60 chiffres, il faut 10 secondes
  • 100 chiffres, il faut une après-midi
  • 200 chiffres, il faut 2 ans, un millier de machines, 50 000€ d’électricité et une équipe d’experts.

Logarithme discret

le contraire de l’exponentiation

Proposition

pour résoudre un logarithme discret \(A=g^a\) dans un groupe d’ordre \(n\)

  • algorithme naïf \(O(n)\)
  • baby-step giant-step \(O(\sqrt n)\)
  • calcul d’indice sur \(\F_q\)
  • réduction de Pohlig-Hellman (lemme chinois) si n est composé