Cryptographie!

Classes de complexité et complexité

  Certains problèmes sont plus difficiles que d'autres. Par exemple, étant donné un nombre, il est très facile de tester si ce nombre est divisible par 2 ou non : il suffit de regarder si le dernier chiffre appartient à l'ensemble {0,2,4,6,8}. En revanche, il est beaucoup plus difficile de déterminer sa décomposition en produits de facteurs premiers.

Définition : Un algorithme est dit en temps polynômial s'il existe deux constantes C et n telles que, pour tout entier n, pour des données de taille n, l'algorithme s'exécute en moins de C.nk opérations élémentaires (les constantes C et k étant bien sûr indépendantes de n).
  Dans la définition précédente, le terme d'opérations élémentaires est assez vague. On doit le comprendre comme des additions, des multiplications, des comparaisons, etc... (tout ce que le processeur sait réaliser en un temps fixe). Ce qu'il faut retenir, c'est que les algorithmes polynômiaux sont les seuls à pouvoir être utilisés informatiquement pour de grandes valeurs de n, et ce, quelle que soit la puissance de la machine.

Définition :
  • On dit qu'un problème est dans P s'il existe un algorithme pour le résoudre en temps polynômial.
  • On dit qu'un problème est dans NP s'il existe un algorithme pour vérifier qu'une solution donnée convient en un temps polynômial.
  La définition d'un problème NP peut sembler complexe. Essayons de l'éclaicir. Un des problèmes difficiles des mathématiques est la factorisation d'un entier en produit de facteurs premiers. On ne sait pas s'il existe un algorithme polynômial qui réussisse cette opération. Autrement dit, on ne sait pas si ce problème est dans P. En revanche, étant donné des nombres p1,...,pk, il est trivial de vérifier si n=p1...pk : ce problème est dans NP.

  Un autre problème classique est celui du voyageur de commerce. Ce voyageur doit visiter n villes pour vendre sa camelote. Il existe entre ces villes un certain nombre de routes. Existe-t-il un trajet permettant de visiter toutes les villes en moins de b kms. C'est un problème difficile, et on ne sait pas s'il existe un algorithme polynômial pour le résoudre. En revanche, si l'on donne un trajet, il est quasi-immédiat de vérifier si ce trajet fait moins de b kms. Le problème est dans NP.

  Pour résumer, être dans P, c'est trouver une solution en temps polynômial, tandis qu'être dans NP, c'est vérifier en temps polynômial qu'une proposition de réponse est une solution du problème. Ainsi, tout problème qui est dans P se trouve dans NP. Un champ de recherche majeur des mathématiques actuelles est le problème de la réciproque : a-t-on P=NP? Autrement dit, peut-on trouver en temps polynômial ce que l'on peut vérifier en temps polynômial? Ce problème est si important qu'il fait partie des 7 problèmes du millénaire, dont la résolution est primée 1 million de dollars par le Clay Mathematic Institute.

Définition : On dit qu'un problème est NP-complet si la résolution de ce problème en temps polynômial entraîne la résolution en temps polynômial de tout problème NP.
  Les problèmes NP-complets sont donc les plus compliqués des problèmes NP. On peut aller jusqu'à douter de leur existence. Pourtant, on sait depuis 1970 qu'il en existe. Le problème du voyageur de commerce en est un. Un autre problème célèbre est celui du sac à dos. Il consiste en la problématique suivante : soient des poids a1,…,an et un poids à atteindre $k$. Est-il possible de trouver parmi les poids a1,…,am certains poids dont la somme fera k. On ne connait pas d'algorithme en temps polynomial pour cela. En revanche, si on choisit certains des poids parmi a1,…,am, il est très facile de vérifier si leur somme fait k. Le problème du sac à dos est un problème NP, et il est NP-complet, c'est-à-dire qu'il est au moins aussi difficile que les autres problèmes NP. Ceci explique pourquoi il est tentant de l'utiliser comme base d'un algorithme de cryptographie à clé publique, ce qu'on fait Merkle et Hellman.
Consulter aussi