From 7d35709eec25c5d67b07004710bb49813f9c4477 Mon Sep 17 00:00:00 2001 From: couchot Date: Thu, 4 Sep 2014 22:27:21 +0200 Subject: [PATCH] ajout d'exos de congruences --- main.tex | 8 ++++ probapremier.py | 23 +++++++++++ rsa.tex | 103 ++++++++++++++++++++++++++++++++++++++++++------ 3 files changed, 123 insertions(+), 11 deletions(-) create mode 100644 probapremier.py diff --git a/main.tex b/main.tex index 59c3391..41c38f3 100755 --- a/main.tex +++ b/main.tex @@ -56,6 +56,14 @@ \newtheorem{Exo}{Exercice}[chapter] +\theoremstyle{plain} +%\theoremsymbol{\ensuremath{\clubsuit}} +\theoremseparator{.} +%\theoremprework{\hrulefill} +%\theorempostwork{\hrulefill\newline} +\newtheorem{Exp}{Exemple}[chapter] + + \theoremstyle{plain} %\theoremsymbol{\ensuremath{\clubsuit}} diff --git a/probapremier.py b/probapremier.py new file mode 100644 index 0000000..3f8cfeb --- /dev/null +++ b/probapremier.py @@ -0,0 +1,23 @@ +import math as m + +st = "\\begin{tabular}{|l|" +lc = [75,100,125,150,175,200,225,250,275,300] +for l in range(len(lc)): + st +="l|" +st +="}\n \hline \n Nombre de chiffres " +for j in lc : + st += "& " + "\\textbf{"+str(j)+"}" +st +="\\\\\n \hline \n Dernier chiffre quelconque " +for j in lc : + st += "& " + str(int(m.log(pow(10,j)))) +st +="\\\\\n \hline \n Dernier chiffre impair " +for j in lc : + st += "& " + str(int(m.log(pow(10,j))*0.5)) +st +="\\\\\n \hline \n Dernier chiffre dans $\\{1,3,7,9\\}$" +for j in lc : + st += "& " + str(int(m.log(pow(10,j))*0.4)) + + +st +="\\\\\n \\hline \\end{tabular}" +print st + diff --git a/rsa.tex b/rsa.tex index cb11f3f..7301393 100644 --- a/rsa.tex +++ b/rsa.tex @@ -296,7 +296,8 @@ d'inconnues $x$ et $y$. \begin{Exo}[Sujet du bac S Liban 2005] -On rappelle le résultat suivant appelé petit théorème de Fermat. +On rappelle le résultat suivant appelé le corollaire du +petit théorème de Fermat. \emph{Si $p$ est un nombre premier et $a$ un entier non divisible par $p$, alors $a^{p-1}-1$ est un multiple de $p$.} @@ -369,10 +370,40 @@ que $ax \equiv 1[n]$. \begin{itemize} \item[\textbf{Existence.}] Comme $a$ et $n$ sont premiers entre eux, d'après le théorème de Bézout, -il exite $x$ et $y$ entiers tels que +il existe $x$ et $y$ entiers tels que +PREUVE A FINIR + + \end{itemize} \end{Proof} +\begin{Exp} +Trouvons les nombres $x$ tels que $7x+11$ soit multiple de 36. Dit autrement, +résoudre l'équation $7x \equiv -11 [36]$. + +On cherche un \og inverse \fg{} de 7 c.-à-d. un nombre $t$, $1 < t < 35$ +tel que $7t \equiv 1 [36]$. +Soit à résoudre $7t \equiv 1 [36]$ qui revient à trouver $t$ et $u$ tels +que $7t -36u = 1$, soit encore les coefficient de Bézout relatifs à +(7 et 36). On trouve successivement +\begin{eqnarray*} +36 & = & 7 \times 5 +1 \\ +7 & = & 7 \times 1 + 0 \\ +& \textrm{et donc}&\\ +1 & = & 36 - 7 \time 5 +\end{eqnarray*} +et donc $t = -5$ (et $u=-1$). +On en déduit $7x \equiv -11 [36]$ est équivalent à +$(-5).7x \equiv (-5).-11 [36]$ soit encore +$x \equiv 55 [36] \equiv 19 [36]$. +\end{Exp} + +\begin{Exo} +Trouver les entiers relatif $x$ tels que +$261x +2$ soit multiple de 305. +\end{Exo} + + \begin{Exo} \begin{enumerate} @@ -385,6 +416,9 @@ il exite $x$ et $y$ entiers tels que \end{enumerate} \end{Exo} + + + \begin{Exo} On se place dans le contexte de cryptographie par RSA. Démontrer que si la clé d'encryptage est $e < \varphi(n)$, alors @@ -419,8 +453,56 @@ a^d & \equiv & (m^e)^d [n]\\ \end{eqnarray*} \end{Proof} + +\begin{Prop}[Petit théorème de Fermat] +Si $p$ est un nombre premier et $a$ un entier +alors $a^{p} \equiv a [p]$. +\end{Prop} + +\begin{Proof} +La preuve se fait par récurrence sur $a$. +\begin{itemize} +\item Pour $a=0$, c'est trivial. +\item Supposons la formule établie pour $k=a$ et montrons qu'elle l'est aussi +pour $k=a+1$. +On remarque tout d'abord que pour chaque $k$, $0 < k < p$, le coefficient +binomial $\binom{p}{k} = \frac{p!}{k!(p-k)!}$ est divisible par $p$, c.-à-d. +$\binom{p}{k} \equiv 0 [p]$. +On a alors successivement: +\begin{eqnarray*} +(k+1)^p &=& a^p + +\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\dots +\binom{p}{p-1}a^{1}+1\\ +&\equiv& a^p +1 [p]\textrm{ (d'après la remarque sur les coeff. binomiaux)}\\\ +&\equiv& a +1 [p]\textrm{ (par hypothèse de récurrence)}\\\ +\end{eqnarray*} +\end{Proof} + +\begin{Prop}[Corrolaire du petit théorème de Fermat] +Si $p$ est un nombre premier et $a$ un entier non divisible par $p$, +alors $a^{p-1}-1$ est un multiple de $p$, +\end{Prop} +\begin{Proof} +D'après le petit théorèmede Fermat, $a^{p} \equiv a [p]$. Dit Autrement +$p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ ne divise pas $a$ d'après les +hypothèses. D'après le théorème de Gau{\ss}, $p$ divise $a^{p-1}-1$. +\end{Proof} + \subsection{Puissance de grands nombres} +\begin{Exp} +Calculons $666^{999}[13]$. +On a successivement: +\begin{eqnarray*} +666^{999} & \equiv & (13\times 51 + 3)^{999} [13]\\ + & \equiv & 3^{999} [13]\\ + & \equiv & 3^{12\times83 +3} [13] \\ + & \equiv & 3^3 \time (3^{12})^{83} [13] \\ + & \equiv & 3^3 \time (1)^{83} [13] \textrm{(car $3^{12}\equiv 1 [13]$ d'après le corollaire du petit théorème de Fermat)}\\ + & \equiv & 27 [13]\\ + & \equiv & 1 [13] +\end{eqnarray*} +\end{Exp} + \begin{Exo} Montrer que l'entier naturel $n$ est premier si et seulement si @@ -428,6 +510,13 @@ $$(x +1) ^n \equiv x ^n +1[n].$$ \end{Exo} + + +\begin{Exo} +Calculer $2^{500} [13]$ et $26^{1000} [17]$. +\end{Exo} + + \section{Génération de grands nombres premiers} Dans ce qui suit, on nomme $\Prem$ l'ensemble des nombrs premiers. Depuis Euclide, on sait que $\Prem$ est de taille infinie. @@ -537,7 +626,7 @@ il suffit de vérifier qu'il nest pas multiple d'un nombre premiers inférieur \subsubsection{Tests probabilistes} -\begin{Prop}[Petit théorème de Fermat] +\begin{Prop}[Corrolaire du petit théorème de Fermat] Si $p$ est un nombre premier et $a$ un entier non divisible par $p$, alors $a^{p-1}-1$ est un multiple de $p$, c'est-à-dire: \begin{equation} @@ -547,14 +636,6 @@ alors $a^{p-1}-1$ est un multiple de $p$, c'est-à-dire: \end{equation} \end{Prop} -\begin{Proof} -La preuve découle directement du théorème~\ref{th:Euler} d'Euleur. -En effet on a successivement: -\begin{eqnarray*} - a^{p-1} & = & a^{\varphi(p)} \textrm{(comme p est premier)}\\ - & \equiv & 1 [p] \textrm{(théorème d'Euler)} -\end{eqnarray*} -\end{Proof} \paragraph{Test de Fermat.} Le petit théorème de Fermat est une implication et non pas une équivalence: -- 2.39.5