Théorie de la complexité

Description

La cryptographie cherche systématiquement à mettre l’adversaire en face
de tâches algorithmiques insurmontables. La question de la caractérisation
des problèmes algorithmiquement difficiles engendre la théorie de la
complexité. Le cours s’articule autour des notions suivantes:

  • Algorithme, machine de Turing
  • Calculabilité, décidabilité
  • Classes de complexité, la classe P, la classe NP
  • Réductions polynomiales, problèmes NP-complets, théorème de Cook
  • la classe PSPACE.

Les bases de la théorie de la complexité préparent aux réductions de sécurité qui
accompagnent les protocoles cryptographiques modernes.

Références

Enseignants

Fiche UE de l’université