Cours sur les nombres premiers

Leçon 1 • Ce qui rend un nombre premier

Définit les nombres premiers par les règles de divisibilité et le comptage des facteurs. Ancre le chapitre en établissant le critère central dont dépendent tous les sujets ultérieurs.

Leçon 2 • Nombres composés et factorisation

Décompose les nombres composés en éléments premiers à l'aide d'arbres de facteurs et de divisions successives. Établit le contraste avec les nombres premiers nécessaire tout au long du cours.

Leçon 3 • Premiers exemples et motifs de nombres premiers

Passe en revue les premiers nombres premiers et les motifs de surface dans leur distribution. Développe l'intuition avant l'introduction de la théorie formelle.

Leçon 1 • PGCD et PPCM par factorisation

Utilise les décompositions en facteurs premiers pour calculer les plus grands communs diviseurs et les plus petits communs multiples. Démontre la valeur pratique immédiate du théorème fondamental.

Leçon 2 • Stratégie de démonstration et lemmes clés

Parcourt la structure de la démonstration en utilisant le lemme d'Euclide comme outil central. Développe les compétences de raisonnement logique appliquées tout au long du cours.

Leçon 3 • Énoncé et signification du théorème

Présente le théorème avec précision et explique pourquoi l'unicité est importante. Établit les bases conceptuelles pour toutes les techniques basées sur la factorisation dans le chapitre.

Leçon 4 • Limites et cas particuliers

Examine où les hypothèses standard de factorisation échouent, y compris le rôle des unités. Prépare les étudiants aux contextes généralisés rencontrés dans les chapitres avancés.

Leçon 1 • Test de primalité de Miller-Rabin

Présente l'algorithme de Miller-Rabin comme un test de primalité probabiliste robuste. Les étudiants apprennent à borner la probabilité d'erreur et à appliquer le test à de grands entiers.

Leçon 2 • Le crible d'Ératosthène

Enseigne le crible classique pour générer efficacement tous les nombres premiers jusqu'à une borne donnée. Introduit le test de primalité par lots comme complément aux méthodes sur un seul nombre.

Leçon 3 • Test de primalité déterministe AKS

Passe en revue l'algorithme AKS comme premier test de primalité déterministe en temps polynomial. Contextualise son importance théorique par rapport à ses cas d'utilisation pratiques.

Leçon 4 • La division par essais en profondeur

Affine l'approche de base de la division par essais avec la borne de la racine carrée et le test des seuls nombres impairs. Établit l'algorithme de référence auquel les méthodes plus rapides sont comparées.

Leçon 1 • Écarts et amas de nombres premiers

Examine l'espacement entre nombres premiers consécutifs, y compris les nombres premiers jumeaux et les grands écarts. Relie les observations empiriques aux conjectures ouvertes en théorie des nombres.

Leçon 2 • Fonction de comptage des nombres premiers

Définit la fonction de comptage des nombres premiers et examine sa croissance à l'aide de données tabulées. Fournit l'outil quantitatif utilisé dans le théorème des nombres premiers.

Leçon 3 • Le théorème des nombres premiers

Énonce et interprète le théorème des nombres premiers et son approximation logarithmique. Donne aux étudiants le résultat asymptotique central régissant la distribution des nombres premiers.

Leçon 4 • Infinité des nombres premiers

Présente la démonstration d'Euclide et des variantes modernes montrant que les nombres premiers ne s'épuisent jamais. Établit le paysage infini dans lequel se posent les questions de distribution.

Leçon 1 • Nombres premiers de Wieferich et de Wall-Sun-Sun

Introduit des classes de nombres premiers rares définies par des conditions de congruence impliquant des puissances et les nombres de Fibonacci. Illustre comment des conditions de primalité exotiques émergent de la théorie profonde des nombres.

Leçon 2 • Nombres premiers de Sophie Germain et nombres premiers sûrs

Définit les nombres premiers de Sophie Germain et leurs nombres premiers sûrs associés. Met en lumière leur rôle dans la conception de protocoles cryptographiques abordé dans les chapitres ultérieurs.

Leçon 3 • Nombres premiers de Mersenne

Étudie les nombres premiers de la forme deux puissance n moins un et leurs conditions nécessaires. Fait le lien avec le test de Lucas-Lehmer et la recherche de grands nombres premiers.

Leçon 4 • Nombres premiers jumeaux et constellations de nombres premiers

Définit les nombres premiers jumeaux et les constellations de nombres premiers plus larges avec des motifs d'écart fixes. Passe en revue le paysage des conjectures et les résultats partiels connus.

Leçon 1 • Application du petit théorème de Fermat

Dérive et applique le petit théorème de Fermat pour les modules premiers dans les calculs. Permet l'exponentiation modulaire rapide et le calcul d'inverses utilisé en cryptographie.

Leçon 2 • Fondements de l'arithmétique modulaire

Passe en revue la notation de congruence, les classes de résidus et les opérations arithmétiques modulo n. Établit le cadre algébrique requis pour tous les résultats sur les modules premiers.

Leçon 3 • Résidus quadratiques et symbole de Legendre

Définit les résidus quadratiques modulo un nombre premier et introduit le symbole de Legendre. Fournit des outils pour déterminer la résolubilité des congruences quadratiques.

Leçon 4 • Théorème d'Euler et fonction indicatrice

Étend le résultat de Fermat aux modules composés à l'aide de l'indicatrice d'Euler. Élargit la boîte à outils pour le calcul modulaire au-delà des modules premiers.

Leçon 1 • Sécurité de RSA et difficulté de la factorisation

Analyse les hypothèses de sécurité de RSA et les attaques connues basées sur les algorithmes de factorisation. Guide les étudiants dans le choix de tailles de clés sûres et de pratiques de génération de nombres premiers.

Leçon 2 • Chiffrement et déchiffrement RSA

Construit l'algorithme RSA depuis la sélection des nombres premiers jusqu'à la génération de clés et la récupération du message. Démontre comment la difficulté de la factorisation en nombres premiers sous-tend la sécurité à clé publique.

Leçon 3 • Notions de base sur la cryptographie à courbes elliptiques

Introduit les courbes elliptiques sur les corps premiers et le problème du logarithme discret sur courbe elliptique. Montre comment des nombres premiers plus petits offrent une sécurité équivalente à celle de RSA.

Leçon 4 • Génération de nombres premiers cryptographiques

Couvre les méthodes pratiques pour générer de grands nombres premiers aléatoires adaptés à un usage cryptographique. Intègre les tests de primalité des chapitres précédents dans un processus de production.

Leçon 1 • Recherche computationnelle sur les nombres premiers

Passe en revue les projets de calcul distribué et les algorithmes qui animent les découvertes record de nombres premiers. Relie les connaissances théoriques aux efforts de calcul à grande échelle actifs.

Leçon 2 • L'hypothèse de Riemann et les nombres premiers

Relie les zéros de la fonction zêta de Riemann à la distribution précise des nombres premiers. Présente l'hypothèse comme le problème ouvert le plus profond reliant l'analyse et la théorie des nombres premiers.

Leçon 3 • Conjecture de Goldbach

Énonce la conjecture de Goldbach et passe en revue la vérification computationnelle et les démonstrations partielles. Illustre comment des énoncés simples sur les nombres premiers peuvent résister à la démonstration pendant des siècles.

Leçon 4 • Nombres premiers dans les suites polynomiales

Étudie si les polynômes peuvent générer une infinité de nombres premiers et les résultats connus. Étend la théorie de la distribution aux suites définies algébriquement.