Cryptology Academy · Leçon

GCD, indicatrice d’Euler et introduction à la théorie des nombres

Appliquez GCD et la fonction indicatrice d’Euler à des problèmes cryptographiques concrets

Leçon 4 sur 413 étapes

GCD, indicatrice d’Euler et introduction à la théorie des nombres est une leçon Cryptology Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Cryptology Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Cryptology Academy comprend 4 leçons au total.

Bienvenue

Le GCD et la fonction indicatrice d’Euler sont des outils essentiels pour RSA et de nombreux autres systèmes à clé publique. Maîtrisons-les à l’aide d’exemples.

Plus grand diviseur commun (GCD)

GCD(a, b) est le plus grand entier qui divise a et b sans reste. GCD(12, 8) = 4. Si GCD(a, m) = 1, nous disons que a et m sont premiers entre eux.

Algorithme d’Euclide

GCD(a, b) = GCD(b, a mod b), avec comme cas de base GCD(a, 0) = a. GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python : import math; math.gcd(48, 18) → 6

Algorithme d’Euclide étendu

La version étendue trouve des entiers x et y tels que ax + by = GCD(a,b). Lorsque GCD(a,m)=1, x est l’inverse modulaire de a modulo m. C’est ainsi que RSA calcule les clés privées.

Fonction indicatrice d’Euler φ(n)

φ(n) compte les entiers de 1 à n qui sont premiers avec n. φ(10) = 4, car {1, 3, 7, 9} sont premiers avec 10. φ(p) = p-1 pour tout nombre premier p.

Indicatrice d’un produit

Pour RSA : n = p×q (p et q premiers). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Exemple : p=5, q=11 : φ(55) = 4×10 = 40. C’est pourquoi factoriser n casse RSA : cela révèle φ(n).

Théorème d’Euler

Si GCD(a,n)=1 : a^φ(n) ≡ 1 (mod n). C’est le fondement mathématique du déchiffrement RSA : M = C^d mod n, car e×d ≡ 1 (mod φ(n)).

Calculer d dans RSA

Choisissez e = 65537 (exposant public RSA courant). Calculez d = e^(-1) mod φ(n) à l’aide de l’algorithme d’Euclide étendu. Vérifiez que e×d mod φ(n) == 1.

Indicatrice en Python

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Lambda de Carmichael

Le RSA moderne utilise la fonction lambda de Carmichael λ(n) = lcm(p-1, q-1) au lieu de φ(n). Elle fournit un module équivalent plus petit. PKCS#1 v2 et NIST recommandent λ(n).

Résumé des applications pratiques

GCD : vérifier que e est premier avec φ(n). Euclide étendu : calculer la clé privée d. Indicatrice : déterminer le groupe des exposants pour l’exponentiation modulaire. Ces trois outils sont utilisés lors de chaque génération de clé RSA.

Vérification rapide

Pour RSA avec p=7 et q=11, quelle est la valeur de φ(n) ?

Réponds-y dans la leçon interactive

Récapitulatif

Excellent ! Le GCD, l’algorithme d’Euclide et l’indicatrice d’Euler font désormais partie de vos outils. Nous allons ensuite étudier XOR et les opérations bit à bit, les briques fondamentales des chiffres symétriques.

Gratuit pour commencer

Apprends Cryptology Academy avec un tuteur IA — gratuit

Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.

Cours: 67
Leçons: 261

Commencer gratuitement Voir le cours complet

Questions Fréquemment Posées

La leçon « GCD, indicatrice d’Euler et introduction à la théorie des nombres » est-elle gratuite ?

Oui — le texte complet de « GCD, indicatrice d’Euler et introduction à la théorie des nombres » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Cryptology Academy, passe à CoddyKit PRO. Le cours Cryptology Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « GCD, indicatrice d’Euler et introduction à la théorie des nombres » ?

Appliquez GCD et la fonction indicatrice d’Euler à des problèmes cryptographiques concrets Tu pratiques Cryptology Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Cryptology Academy ?

Aucune expérience préalable n'est requise. Cryptology Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « GCD, indicatrice d’Euler et introduction à la théorie des nombres » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Cryptology Academy ?

Oui. Chaque leçon Cryptology Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

Bases du binaire et de l’hexadécimal
Bases de l’arithmétique modulaire
Nombres premiers et factorisation
GCD, indicatrice d’Euler et introduction à la théorie des nombres

← Retour à Cryptology Academy