Séance de cours
Exposentiation: Complexité temporelle
Description
Cette séance de cours explique l'algorithme d'exponentiation rapide pour le calcul de l'AB, où B est décomposé sous forme binaire et le calcul implique la quadrature A plusieurs fois suivie par la multiplication. La complexité temporelle est O(n3) pour AB (mod N) si N a n chiffres. La version récursive de l'algorithme est discutée, avec les propriétés des nombres premiers et le schéma de cryptage El-Gamal.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.