Compétence · Terminale TE.CONG.CRYPT.01 Niveau : Expert

Appliquer le petit théorème de Fermat : test de Fermat, nombres de Mersenne, RSA

Montrer qu'un entier n'est pas premier avec le test de Fermat (la contraposée du théorème), en se méfiant des témoins menteurs ; nombres de Mersenne 2ᵖ − 1 ; chiffrement RSA sur un petit exemple : clés, chiffrement et déchiffrement.

Chapitre : Nombres premiers et petit théorème de Fermat Filière : Term Maths Expertes Temps de maîtrise : ~90 min

Le cours

Applications : test de Fermat, Mersenne, RSA~1 min

À retenir — test de Fermat (contraposée)

Si l'on trouve un entier $a$, $1\lt a\lt n$, tel que $\boldsymbol{a^{n-1}\not\equiv1\ [n]}$, alors $n$ n'est pas premier ($a$ est un témoin de Fermat). La réciproque est fausse : $2^{340}\equiv1\ [341]$ alors que $341=11\times31$ ; le test rend la primalité probable, il ne la prouve jamais.

Exemple

Nombres de Mersenne $M_n=2^n-1$ : $M_2=3$, $M_3=7$, $M_5=31$, $M_7=127$ sont premiers, mais $M_{11}=2047=23\times89$ ne l'est pas. Si $n=ab$ est composé, $2^a-1$ divise $2^n-1$ (factorisation de $x^b-1$) : $M_n$ premier $\Rightarrow$ $n$ premier, sans réciproque. Les plus grands premiers connus sont des nombres de Mersenne.

Exemple

Principe du chiffrement RSA (problème possible du programme). Deux premiers $p\neq q$, $n=pq$ ; $e$ premier avec $(p-1)(q-1)$ et $d$ inverse de $e$ modulo $(p-1)(q-1)$. Clé publique $(n,e)$ : $c\equiv m^e\ [n]$. Clé privée $d$ : $m\equiv c^d\ [n]$. La correction $m^{ed}\equiv m\ [n]$ repose sur Fermat modulo $p$ et modulo $q$, puis sur Gauss ($p\wedge q=1$) ; la sécurité, sur la difficulté de factoriser $n$.

Conçu et validé par Laurent Jacquet, professeur de mathématiques. Qui conçoit les cours ?

Entraîne-toi sur ce cours

Avec un compte gratuit : les QCM et ta Konfiance après chaque question, et le sentier complet d'un chapitre au choix, rappels et épreuve compris.

S'inscrire gratuitement

Déjà inscrit ? Se connecter

Pour aller plus loin

Maîtrise cette compétence avec Konfia

Tous les sentiers, tous les corrigés détaillés et les rappels de révision : 29 € l'année, ou 4,99 € par mois.

Voir l'abonnement