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é :
On utilise les notations \(O(\;)\) pour estimer seulement le terme dominant de ces mesures.
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.
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\))
multiplication
complexité de la multiplication de deux entiers de \(n\) chiffres (resp. de deux polynômes de degré \(n\))
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)
multiplication dans \(M_n(K)\)
en termes d’opérations élémentaires de \(K\) (surtout multiplication)
Proposition
Note
un principe
Si on sait ramener un problème à un problème d’algèbre linéaire, on a «gagné».
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})\)
Proposition
pour factoriser un entier \(N\) de \(n\) chiffres dont le plus petit facteur premier est \(p\leq\sqrt N\).
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.
le contraire de l’exponentiation
Proposition
pour résoudre un logarithme discret \(A=g^a\) dans un groupe d’ordre \(n\)