Introduction to number theory lecture 16. More numerical calculation

Item: Introduction to number theory lecture 16. More numerical calculation
Rating: 5
Author: PostSingularity Institute

par Richard E Borcherds

Sciences formelles & physiques Mathématiques PBMathématiques PBHThéorie des nombres

🎙 Richard E Borcherds 👥 82K 📅 9 février 2022 ⏱ 25 min 👁 5K 📄 cours magistral 🧭 2026-08-17

Disponible en : Français (actuel) English

Mots-clés

racine carrée modulo palgorithme probabilistetest de primalité de Miller-Rabinfactorisation de Fermatnombres de Carmichael

Résumé

Dans cette seizième leçon du cours d’introduction à la théorie des nombres de Berkeley, Richard Borcherds présente plusieurs algorithmes numériques fondamentaux. Il commence par la recherche d’une racine carrée de -1 modulo un nombre premier p. Il rappelle la formule de Wilson qui donne une solution mais est inefficace pour de grands p. Il propose alors un algorithme probabiliste : choisir un entier b au hasard, calculer b^((p-1)/2) mod p ; si cela vaut -1, alors b^((p-1)/4) est une racine carrée de -1. Chaque essai a environ 50% de chances de réussir, donc en moyenne deux essais suffisent. Il illustre avec p=41. Ensuite, il aborde la factorisation par différence de carrés, méthode attribuée à Fermat, et montre sur l’exemple 7313 = 103 × 71. Il souligne que cette méthode est efficace lorsque les deux facteurs sont proches, mais inefficace en général. Enfin, il améliore le test de primalité de Fermat pour détecter les nombres de Carmichael. Il explique comment, en écrivant m-1 = 2^c * d avec d impair, et en calculant b^d, b^(2d), b^(4d), …, on peut détecter un nombre composé si l’on trouve une racine carrée non triviale de 1. Il illustre avec le nombre de Carmichael 561, où l’on trouve que 67 est une racine carrée de 1 non triviale, prouvant que 561 n’est pas premier. Il conclut en présentant le test de primalité probabiliste qui en résulte, souvent efficace même pour les nombres de Carmichael.

239 mots

Évaluation critique

Valeur des informations & solidité de l’argumentation

La valeur des informations est élevée : le cours présente des algorithmes classiques et fondamentaux en théorie algorithmique des nombres, avec des explications claires et des exemples concrets. L’argumentation est solide : chaque algorithme est justifié par des raisonnements mathématiques rigoureux, et les limites (complexité, cas défavorables) sont explicitement discutées. L’utilisation d’exemples numériques (41, 7313, 561) permet de bien comprendre le fonctionnement des méthodes. La présentation est pédagogique et progressive, allant du problème simple à des améliorations plus sophistiquées.

Rigueur scientifique, qualité des sources, adéquation du titre

La rigueur scientifique est excellente : le cours s’appuie sur des résultats classiques de la théorie des nombres (théorème de Wilson, petit théorème de Fermat, propriétés des racines de l’unité modulo un premier). Les algorithmes sont présentés avec leurs justifications mathématiques, et les cas particuliers (nombres de Carmichael) sont traités avec soin. Les sources sont implicites mais fiables : le cours est basé sur le manuel de Niven, Zuckerman et Montgomery, et le professeur est un mathématicien reconnu. L’adéquation entre le titre et le contenu est parfaite : la leçon est bien une introduction à la théorie des nombres, et le thème des calculs numériques est central. Aucune publicité n’est présente dans la vidéo.

208 mots

Adéquation titre / contenu

Le titre correspond parfaitement au contenu : il s'agit bien d'une introduction à la théorie des nombres, et la seizième leçon est consacrée à des calculs numériques supplémentaires.

Qualité & fiabilité

9/10

Cours universitaire de niveau licence (Berkeley Math 115) par un mathématicien reconnu, avec démonstrations rigoureuses et algorithmes explicités. Les résultats sont classiques et vérifiables dans la littérature.

Moments clés

Repères établis par PSI à partir de la transcription : le créateur n'a pas défini de chapitres.

Sources citées

Playlist du cours Math 115 — Référence aux autres leçons du cours.

Sources concordantes

An Introduction to the Theory of Numbers — Manuel de référence du cours, mentionné dans la description.

Apport & nouveautés

Cette leçon apporte une présentation claire et pédagogique d’algorithmes fondamentaux en théorie algorithmique des nombres, avec des exemples numériques détaillés. L’accent est mis sur l’efficacité pratique et les limites théoriques, notamment pour les algorithmes probabilistes. L’originalité réside dans la manière dont l’auteur relie les concepts théoriques (théorème de Wilson, racines de l’unité) à des méthodes de calcul concrètes.

Pour aller plus loin :

Théorème de Wilson — Base théorique pour la formule de la racine carrée.
Test de primalité de Miller-Rabin — Généralisation du test présenté, largement utilisé.
Méthode de factorisation de Fermat — Technique de différence de carrés.
Nombre de Carmichael — Nombres composés qui passent le test de Fermat.

111 mots

Profil radar

Le profil radar montre un contenu très équilibré, avec des scores élevés en qualité, fiabilité et niveau technique, et un score légèrement inférieur en quantité d'information, ce qui reflète une leçon dense mais ciblée sur quelques algorithmes.

Fiabilité 9/10