Algorithmes

Complexité des opérations élémentaires

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 :

Proposition

Soit \(b\geq 2\) un entier. Alors pour tout \(N\geq 0\), il existe une unique suite finie \(d_0,\dots d_n\in\set{0,b-1}^{n-1}\times\set{1,b-1}\) telle que

\[N = \sum_{i=0}^n d_i b^i.\]

De plus, \(n=\floor{\log_b(N)}\) et l’on obtient les \(d_i\) par divisions euclidiennes successives.

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.

Définition

Soit \(x\) un objet de taille \(n\). Un algorithme est dit :

  • polynomial s’il nécessite \(O(n^k)\) opérations élémentaires, pour un certain \(k\geq1\).

  • exponentiel s’il nécessite \(O(e^{\lambda n})\) opérations élémentaires, pour un certain \(\lambda > 0\).

  • sous-exponentiel d’exposant \(0<\alpha<1\) s’il nécessite

    \[O(e^{ c n^\alpha \log(n)^{1-\alpha} }\]

    opérations élémentaires, pour une certaine constante \(c>0\).

opérations usuelles

Soient des objects de tailles \(n_1\) et \(n_2\) avec \(n_1,n_2\leq n\). On a les complexités suivantes :

  • \(A(n)\) : addition dans \(\Z_{\leq 2^n}\) ou \(\K_{\leq n}[x]\)

    • \(O(n)\) («linéaire»)

  • \(M(n)\) : multiplication dans \(\Z_{\leq 2^n}\) ou \(\K_{\leq n}[x]\)

    • algorithme naïf \(O(n^2)\) («quadratique») (pour des objets de taille \(n_1\) et \(n_2\), vaut \(O(n_1n_2)\)).

    • décomposition de Karatsuba \(O(n^{1.58})\)

    • algorithme de Shönhage-Strassen (FFT) \(O(n\log(n)\log\log(n)^2)\) («quasi-linéaire»)

    • algorithme Harvey-VanDerHoeven (FFT) \(O(n\log(n))\) [HVDH20].

  • multiplication dans \(M_n(\K)\)

    • algorithme naïf \(O(n^3)\)

    • décomposition de Strassen \(O(n^{2.81})\)

Remarque

Une étude plus fine de la croissance des coefficients (qui dépend de la suite d’opérations réalisées) est nécessaire pour calculer la complexité binaire des opérations sur \(\Z[X]\).

Exponentiation rapide

Le calcul de \(x^n\) dans un groupe \(G\) se fait de manière naïve en \(n-1\) multiplications dans \(G\).

On peut réduire ce nombre à \(2\log_2(n)\) opérations.

Pour développer cette idée, décomposons \(n\) en base deux

\[n=e_0+e_1 2+e_2 4+\dots e_{k-1} 2^{k-1}+2^k\]

on peut écrire

\[\begin{aligned} a^n &= a^{\sum e_i 2^i}\\ &= a^{e_0} \times (a^2)^{e_1} \times \dots (a^{2^k})^{e_k}\\ &= a^{e_0} \bigl( a^{e_1} \bigl(\dots a^{e_k}\bigr)^2\dots\bigr)^2\bigr)^2. \end{aligned}\]

Dans les deux dernières lignes, l’expression ne fait plus intervenir que \(k\) carrés et au plus \(k+1\) multiplications, avec \(k=\floor{\log_2(n)}\) (plus précisément, \(k\) carrés et un nombre de multiplications égal au nombre de \(1\) dans l’écriture binaire de \(n\)).

Exemple

Calcul des trois derniers chiffres de \(3^n\) en base 10.

  • méthode naïve, produit dans \(\Z\)

    \[\sum_{k=1}^{n-1} O(k) = O(n^2)\]
  • exponentiation rapide dans \(\Z\)

    \[\sum_{k=0}^{\floor{\log_2(n)}} M(2^k) = O(n\log(n))\]
  • exponentiation rapide dans \(\Z/1000\Z\)

    \[\log(n)M(1) = O(\log n)\]

Application: ordre d’un élément

Proposition

Soit \(x\) un élément d’un groupe, et soit \(n > 0\). Alors \(x\) est d’ordre \(n\) si et seulement si

  • \(x^n = 1\)

  • \(\forall p\mid n\), \(p\) premier, \(x^{n/p}\neq 1\).

Application

On détermine un générateur de \(\F_q^\times\) en vérifiant que son ordre est l’ordre attendu.

Exemple

Avec un ordinateur, exhiber un générateur de \(\F_{256}^\times\).


        
        

Application: suites récurrentes

Pour calculer le \(n\)-ième terme de la suite de Fibonacci, ou plus généralement d’une suite récurrente, on écrit

\[(f_{n+1},f_{n}) = (f_n,f_{n-1})\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}\]

soit pour \(n\geq 1\)

\[(f_n,f_{n-1}) = (1,1) A^{n-1}\]

Le calcul se fait en \(O(\log(n)\) étapes au lieu de \(O(n)\).

Avec la même idée, mais un formalisme différent, on détermine le nombre \(f_n\) en calculant

\[x^n.(f_0,f_1,\dots) = (x^n \mod x^2-x-1).(f_0,f_1,\dots)\]

soit

f(n) = polcoeff(lift(Mod(x,x^2-x-1)^n*(1+x)),0)

Algorithme d’Euclide

On note \(R\) un anneau euclidien, qui sera dans ce cours \(\Z\) ou \(\k[x]\).

Proposition

Soient \(a,b\in\Z\), on définit \(r_0,r_1=a,b\) et pour \(k\geq 1\) tel que \(r_k>0\) on définit \(r_{k+1}\) par la division euclidienne

(1)\[r_{k-1} = q_kr_k+r_{k+1},\text{ où }0\leq r_{k+1}\lt r_k\]

Alors il existe \(k\) tel que \(r_{k+1}=0\), auquel cas \(r_k=\pgcd(a,b)\).

Démonstration

D’une part \(\pgcd(r_{k-1},r_k) = \pgcd(r_k, r_{k+1})\), d’autre part \(r_k\) est strictement décroissant dans \(\N\), d’où la terminaison.

Si l’on veut obtenir une relation de Bézout \(au+bv=d\) il est commode d’introduire la famille de relations \(au_k+bv_k=r_k\) où par linéarité \(u_k\) et \(v_k\) obéissent à la récurrence donnée par (1)

(2)\[\begin{pmatrix}u_{k+1}\\v_{k+1}\\r_{k+1}\end{pmatrix} = \begin{pmatrix}u_{k-1}\\v_{k-1}\\r_{k-1}\end{pmatrix} - q_k \begin{pmatrix}u_{k}\\v_{k}\\r_{k}\end{pmatrix}\]

Exemple

Calculons une relation de Bezout entre \(2^{13}-1\) et \(2^8-1\).

On écrit le tableau suivant, où l’on passe d’une ligne à la suivante avec (2)

\(k\)

\(q_k\)

\(r_k\)

\(u_k\)

\(v_k\)

0

\(2^{13}-1\)

1

0

1

\(2^5\)

\(2^8-1\)

0

1

2

\(2^3\)

\(2^5-1\)

1

\(-2^5\)

3

\(2^2\)

\(2^3-1\)

\(-2^3\)

\(1 + 2^8 \)

4

\(2^1\)

\(2^2-1\)

\(1+2^5\)

\(-2^5- 2^2 - 2^{10} \)

5

1

\(-2^3-2-2^6\)

\(1+2^8+2^6+2^3+2^{11}\)

Soit la relation (en base 2)

\[1 = -1001010 \times 1111111111111 + 100101001001 \times 11111111\]

qui reste valable en base 10.

complexité sur $Z$

Soient \(a>b>0\). Le nombre d’itérations de l’algorithme d’Euclide (étendu) vérifie

\[k\leq \log_\phi(b)+1\]

\(\phi\) est le nombre d’or

\[\phi=\frac{\sqrt{5}+1}2\approx 1.618.\]

Démonstration

Cela correspond à l’étude du pire cas \(q_k=1\), donné par la suite de Fibonacci \(f_{n+1}=f_n+f_{n-1}\).

Notons en effet \(R_j=r_{k-j}\) pour \(-1\leq j\leq k\). Alors on a \(R_{-1}=0\), \(R_{0} \geq 1\) et pour tout \(j\), \(R_{j+1} = q_{k-j}R_j+R_{j-1}\geq R_j+R_{j-1}\), donc par récurrence \(R_j\geq f_j\) pour tout \(j\). En particulier, \(b=r_{1}=R_{k-1}\geq f_{k-1}\).

Or l’expression exacte \(f_k = \frac{\phi^{k+1}-(1-\phi)^{k+1}}{2\phi - 1}\) donne \(f_k\geq \phi^n\).

On en déduit que \(k-1\leq \log_\phi(b)\).

Proposition

La complexité de l’algorithme d’Euclide est de \(O(\log(a)\log(b)\) opérations.

cas des polynômes

Soient \(a,b\in \Ax\), avec \(\deg(a)>\deg(b)\). L’algorithme d’Euclide nécessite \(O((1+deg(a))(1+\deg(b))\) opérations \(+,\times,/\) dans \(A\).

Démonstration

La suite des degrés est strictement décroissante, donc l’algorithme s’arrête en moins de \(\deg(b)\) itérations, et chaque itération fait intervenir des polynômes de degré inférieurs à \(\deg(a)\).

Remarque

cet énoncé ne rend pas compte de la complexité réelle dans \(\Z[X]\) ou \(\Q[X]\), où a lieu une explosion des coefficients.

Applications

Inverse modulaire:

  • calculer l’inverse de 7 modulo 103

  • calculer l’inverse de a+1 dans \(\F_3[a]/a^3-a-1\).

Lemme chinois, voir ci-dessous.

Versions rapides

Une stratégie diviser pour régner appliquée à l’algorithme d’Euclide permet de passer à une complexité quasi linéaire :

Proposition

On peut calculer le pgcd de deux entiers de taille \(n\) en \(O(M(n)\log(n))\) opérations.

On peut calculer le pgcd de deux polynômes de degré \(n\) en \(O(M(n)\log(n))\) opérations de \(A\).

Démonstration

Admis, algorithme de Lehmer pour les entiers, de Knuth, Shönhage, … en général.

Lemme chinois

Proposition

Soit \(R\) un anneau euclidien, et \(m_1,\dots m_r\) des éléments de \(R\) deux à deux premiers entre eux.

Alors en notant \(m=\prod m_i\), on a un isomorphisme d’anneaux

\[\pi:\deffunc{R/\langle m\rangle}{\prod R/\langle m_i\rangle}{x}{(x\bmod m_i)_i}\]

Proposition

Pour \(1\leq i\leq r\), on pose \(M_i = \prod_{j\neq i} m_j\) et on calcule une relation de Bézout \(M_iu_i+m_iv_i=1\). Alors l’application

\[\rho:\deffunc{\prod R/\langle m_i\rangle}{R/\langle m\rangle}{x_1,\dots x_m}{\sum x_i u_i M_i}\]

est l’inverse de \(\pi\).

Démonstration

On a bien \(\pi\circ\rho(x_1,\dots x_r)=(x_1,\dots x_r)\) en écrivant \(M_j\equiv 0\bmod m_i\) pour \(j\neq i\) et \(u_iM_i\equiv 1\bmod m_i\) sinon.

Naïvement, les algorithmes de calcul de réduction modulaire ou de reste chinois sont en \(O(n^2)\). On peut toutefois faire mieux :

Théorème

Si \(\sum \abs{m_i}\leq n\), on peut calculer des images \(\pi(x)\) ou \(\rho(x_1,\dots x_r)\) en \(O(M(n)\log(n)\) opérations élémentaires relativement à \(R\).

Méthode de Newton

Version classique

En analyse, la méthode de Newton consiste à approcher numériquement la solution d’une équation \(f(x)=0\) en la linéarisant au voisinage d’un point \(x_0\) non critique :

\[f(x_0)+f'(x_0)(x-x_0) = 0\]

ce qui fournit une approximation

\[x_1 = x_0 - f'(x_0)^{-1}f(x_0).\]

On recommence en réinjectant.

S’il existe une solution \(f(x)=0\) telle que \(f'(x)\neq 0\), on montre que le schéma converge pour tout \(x_0\) appartenant à un certain voisinage de \(x\), et que la convergence est quadratique : il existe \(C>1\) tel que \(\abs{x_n-x}\leq C^{-2^n}\), de sorte que le nombre de chiffres corrects double à chaque itération.

Exemple

Pour calculer la racine carrée d’un réel \(a>0\), on écrit cette racine comme solution de l’équation \(f(x)=0\) pour \(f(x)=x^2-a\). Ceci donne l’itération \(x_{n+1}=\frac{x_n+a/x_n}2\). Une petite étude analytique («suites de la forme \(x_{n+1}=f(x_n)\)») montre que la convergence \(x_n\to \sqrt{a}\) a lieu pour toute valeur \(x_0\geq 0\).

Exemple

Une application plus surprenante : la méthode de Newton permet de calculer l’inverse d’un réel \(a\in\R^\times\) sans effectuer de division. Exercice.

Grâce à la méthode de Newton, la complexité du calcul d’une racine ou de l’inverse est de \(O(M(n))\), où \(M(n)\) est la complexité de la multiplication. On devrait avoir un facteur supplémentaire \(\log(n)\) pour compter le nombre d’étapes : ce n’est pas le cas si on effectue chaque étape avec une précision qui double pour atteindre la précision du résultat, la complexité est alors \(\sum_k O(M(n/2^k)) = O(M(n))\).

Exemple

Les algorithmes de calcul de racine ou d’inverse décrits dans \(\R\) permettent de calculer des racines entières ou des divisions euclidiennes en \(O(n)\), il suffit d’effectuer le calcul jusqu’à une précision suffisante pour identifier la partie entière du résultat.

Lemme de Hensel

Ce schéma se transpose parfaitement au monde de l’algèbre, dans lequel les notions de convergence sont plus diverses et plus faciles à obtenir. Quand on travaille pour une valuation \(p\)-adique, il prend le nom de relèvement de Hensel.

Proposition

On considère un entier \(m\) et un polynôme \(P(x)\in\Z[x]\) tel qu’il existe \(a\in Z\) vérifiant \(P(a)\equiv0\bmod m\) et \(P'(a)\in(\Z/m\Z)^\ast\). Alors pour tout \(k\geq 0\), il existe \(a_k\in\Z\) tel que

\[P(a_k) \equiv 0\bmod m^{2^k}.\]

La suite \(a_k\) est donnée par \(a_0=a\) puis la récurrence

(3)\[a_{k+1} = a_k - P'(a_k)^{-1}P(a_k) \bmod m^{2^k}\]

Démonstration

On utilise la formule de Taylor exacte

Par récurrence, il suffit de montrer qu’avec les hypothèses, en posant \(b=a-P'(a)^{-1}P(a)\bmod m^2\), on a

  • \(b\equiv a \bmod m\), et donc \(\pgcd(P'(b),m)=1\) ;

  • \(P(b)\equiv 0\bmod m^2\).

Le premier point découle de \(P(a)\equiv 0\bmod m\), le second de la formule de Taylor \(P(b)=P(a)+P'(a)(b-a)\bmod m^2\) (car \(m^2\mid (b-a)^2\)).

On remarque que l’équation de récurrence (3) est écrite modulo \(m^2\), mais qu’il suffit de calculer un inverse \(P'(a)^{-1}\bmod m\). En effet, \(P(a)\) est en facteur de \(P(b)\), l’autre terme \((1-P('a)^{-1}P'(a))\) n’a besoin d’être nul que modulo \(m\).

Plus généralement, on peut remplacer dans la proposition \(\Z\) par un anneau de polynômes \(A[x]\) et \(m\) par \(x^n\).

Proposition

Soit \(A\) un anneau, \(f\in A[x,y]\). Soit \(P\in A[x]\) tel que \(f(x,P(x))\equiv 0\bmod x^n\) et \(\pgcd(\frac{\partial P}{\partial y}(x,P),x)=1\). Alors il existe \(Q\equiv P\bmod x^n\) tel que \(f(x,Q)\equiv 0\bmod x^{2n}\).