0Pricing
Cryptology Academy · Leçon

Nombres premiers et factorisation

Découvrez pourquoi les nombres premiers sont au cœur de la cryptographie à clé publique

Nombres premiers et factorisation est une leçon Cryptology Academy gratuite sur CoddyKit. Ceci est la leçon 3 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

Les nombres premiers ne sont divisibles que par 1 et par eux-mêmes. Ce sont les atomes de la multiplication, ainsi que le fondement de RSA, de Diffie-Hellman et de nombreux autres systèmes cryptographiques.

Définition et exemples

Nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... Un nombre est premier si ses seuls diviseurs positifs sont 1 et lui-même. Par convention, 1 n’est NOT premier.

Théorème fondamental de l’arithmétique

Tout entier > 1 peut être factorisé en nombres premiers d’une seule manière, à l’ordre près. 60 = 2² × 3 × 5. Cette unicité permet aux systèmes cryptographiques fondés sur la factorisation de fonctionner.

Division par essais

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True Il suffit de vérifier jusqu’à √n : si aucun facteur n’est trouvé en dessous de √n, n est premier.

Crible d’Ératosthène

Pour trouver tous les nombres premiers jusqu’à N : commencez par une liste de nombres allant de 2 à N. Barrez les multiples de 2, puis ceux de 3, puis ceux de 5, et ainsi de suite. Les nombres restants sont premiers. La complexité est O(N log log N).

Épreuve de primalité : Miller-Rabin

Pour les grands nombres (2048 bits), la division par essais est trop lente. Miller-Rabin est une épreuve probabiliste : exécutez-la 40 fois et la probabilité d’erreur est < 4^(-40).

Factorisation des entiers

Étant donné n = p × q, trouver p et q constitue le problème de la factorisation des entiers. Si n fait 2048 bits, les meilleurs algorithmes connus nécessitent 2^112 opérations, ce qui est actuellement irréalisable.

Pourquoi RSA utilise deux grands nombres premiers

Le module RSA est n = p × q. Connaître n sans connaître p et q rend difficile le calcul de la clé privée. La sécurité repose entièrement sur la difficulté de factoriser n.

Générer de grands nombres premiers

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Oracle: generate random odd number, test with Miller-Rabin, repeat until prime.

Nombres premiers sûrs et forts

Un nombre premier sûr p = 2q+1, où q est également premier. Les nombres premiers sûrs résistent à certaines attaques contre DH. RSA utilise parfois des nombres premiers forts pour empêcher l’attaque de Pollard p−1.

Écarts entre nombres premiers et infinité

Euclide a démontré qu’il existe une infinité de nombres premiers en 300 BCE. La conjecture des nombres premiers jumeaux (il existe une infinité de nombres premiers p et p+2) n’est toujours pas démontrée. Nous ne manquerons jamais de nombres premiers pour la cryptographie.

Vérification rapide

Pourquoi RSA utilise-t-il de grands nombres premiers ?

Récapitulatif

Vous comprenez les nombres premiers et la factorisation. Nous allons ensuite appliquer la fonction indicatrice d’Euler et le GCD, les derniers outils mathématiques nécessaires avant RSA.

Questions Fréquemment Posées

La leçon « Nombres premiers et factorisation » est-elle gratuite ?

Oui — le texte complet de « Nombres premiers et factorisation » 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 « Nombres premiers et factorisation » ?

Découvrez pourquoi les nombres premiers sont au cœur de la cryptographie à clé publique 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 3 sur 4.

Combien de temps prend la leçon « Nombres premiers et factorisation » ?

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

  1. Bases du binaire et de l’hexadécimal
  2. Bases de l’arithmétique modulaire
  3. Nombres premiers et factorisation
  4. GCD, indicatrice d’Euler et introduction à la théorie des nombres
← Retour à Cryptology Academy