Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Exposentiation

Dans cours

MATH-489: Number theory II.d - Cryptography

. ...

Description

Cette séance de cours couvre le concept d'exponentiation, de chiffrement et de décryptage RSA, de grande multiplication d'entiers, d'algorithme Schönhage-Strassen, et l'utilisation de racines primitives. Il explique le calcul de x^y, les propriétés du chiffrement RSA, et les défis de travailler avec les racines primitives.

Enseignant·e

Dimitar Petkov Jetchev

Source officielle

Concepts associés (26)

Chiffrement

thumb|Table de chiffrement de la guerre franco–prussienne de 1870, évoquant une série de mots classés par ordre alphabétique. Archives nationales de France. Le chiffrement (ou parfois cryptage) est un procédé de cryptographie grâce auquel on souhaite rendre la compréhension d'un document impossible à toute personne qui n'a pas la clé de chiffrement. Ce principe est généralement lié au principe d'accès conditionnel. Bien que le chiffrement puisse rendre secret le sens d'un document, d'autres techniques cryptographiques sont nécessaires pour communiquer de façon sûre.

Exponentiation modulaire

En mathématiques, plus précisément en arithmétique modulaire, l’exponentiation modulaire est un type d'élévation à la puissance (exponentiation) réalisée sur des entiers modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le domaine de la cryptologie. Etant donnés une base b, un exposant e et un entier non nul m, l'exponentiation modulaire consiste à calculer c tel que : Par exemple, si b = 5, e = 3, et m = 13, le calcul de c donne 8.

Algorithme de Karatsuba

En informatique, l'algorithme de Karatsuba est un algorithme pour multiplier rapidement deux nombres de n chiffres avec une complexité temporelle en O(n) ≈ O(n) au lieu de O(n) pour la méthode naïve. Il a été développé par Anatolii Alexevich Karatsuba en 1960 et publié en 1962 . Pour multiplier deux nombres de n chiffres, la méthode naïve multiplie chaque chiffre du multiplicateur par chaque chiffre du multiplicande. Cela exige donc n produits de deux chiffres. Le temps de calcul est en O(n2).

Exponentiation

En mathématiques, l’exponentiation est une opération binaire non commutative qui étend la notion de puissance d'un nombre en algèbre. Elle se note en plaçant l'un des opérandes en exposant (d'où son nom) de l'autre, appelé base. Pour des exposants rationnels, l'exponentiation est définie algébriquement de façon à satisfaire la relation : Pour des exposants réels, complexes ou matriciels, la définition passe en général par l'utilisation de la fonction exponentielle, à condition que la base admette un logarithme : L'exponentiation ensembliste est définie à l'aide des ensembles de fonctions : Elle permet de définir l'exponentiation pour les cardinaux associés.

Algorithme de multiplication d'entiers

Les algorithmes de multiplication permettent de calculer le résultat d'une multiplication. Graphiquement, il s'agit de transformer un rectangle multiplicateur × multiplicande en une ligne, en conservant le nombre d'éléments. Ce type de multiplication n'utilise que des additions et des multiplications ou des divisions par 2. Elle ne nécessite pas de connaître de table de multiplication (autre que la multiplication par 2).

Afficher plus

Séances de cours associées (33)

Multiplication de Montgomery

Couvre la réduction Barrett, la forme Montgomery des entiers, et le calcul efficace du produit Montgomery.

Groupes cycliques : structure et applications

Explore en profondeur les groupes cycliques, les générateurs, les isomorphismes et le problème du logarithme discret, en soulignant leur importance et leurs applications.

Algorithmes et croissance des fonctions

Couvre les algorithmes d'optimisation, l'appariement stable et la notation Big-O pour l'efficacité de l'algorithme.

Exposentiation: Complexité temporelle

Couvre l'algorithme d'exponentiation rapide et sa complexité temporelle, les propriétés des nombres premiers et le schéma de cryptage El-Gamal.

Nombres premiers et algorithmes

Couvre les nombres premiers, les algorithmes de test de primalité, l'arithmétique modulaire et les méthodes d'exponentiation efficaces.

Afficher plus

Concepts associés (26)

Chiffrement

Exponentiation modulaire

Algorithme de Karatsuba

Exponentiation

Algorithme de multiplication d'entiers

Afficher plus