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é