Calculs et complexité

Complexité

Soit \(N\) un entier. On peut représenter sa valeur sur \(n=\floor{\log_2(N)}+1\) bits, on dit que \(N\) est de taille \(n\) (ceci est valable pour toute base).

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.

Soit \(P(x)\in A[x]\) un polynôme de degré \(n\) à coefficients dans un anneau \(A\). On peut représenter \(P\) à l’aide de \(n+1\) coefficients dans \(A\), ont dit que \(P\) est de taille \(n\) sur \(A\). Une opération élémentaire relativement à \(A[X]\) est une opération \(+,-,\times\) de \(A\).

On mesure la complexité d’un algorithme en nombre d’opérations élémentaires.

Quelques grands problèmes

Multiplication

multiplication dans $Z$

complexité de la multiplication de deux entiers de \(n\) chiffres

  • 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 multiplier dans \(\Z\), on sait aussi

  • prendre des puissances (exponentiation)

  • diviser (cf. plus loin)

  • calculer des pgcd, des relations de Bézout

  • manipuler les entiers, les polynômes, les matrices, les séries…

  • pour des coefficients dans \(\Z\), \(\Q\), \(\R\), \(\F_q\),…

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 \(O(n^3)\)

  • polynôme caractéristique, inversion \(O(n^4)\)

  • calculs d’image, de noyau, résolution de systèmes linéaires

Tout est polynomial, avec des exposants raisonnables.

Note

premier principe

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

Factorisation (d’entiers)

le contraire de la multiplication

Définition

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

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

  • \(L_n(0,c) = d^c = \log(n)^c\), complexité polynomiale d’exposant \(c\)

  • \(L_n(1,c) = e^{cd} = n^c\), complexité exponentielle de facteur \(c\)

Proposition

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

  • divisions \(O(p)=O(\sqrt n)\) 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

second principe

En théorie algorithmique des nombres, c’est souvent sur la factorisation d’entiers qu’on bloque (discriminant d’un corps de nombre en particulier)

  • 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é