ajout de qques exos

diff --git a/main.tex b/main.tex
index 244a854abd46b7c64bee000b4914e9e39848f0a1..22badb067fc1f2f564c99e01c5d49a8a9b013475 100755 (executable)
--- a/main.tex
+++ b/main.tex
@@ -38,14 +38,14 @@
 
 
 
 
 
 

-\theoremstyle{plain}
+\theoremstyle{nonumberplain}

 \theoremheaderfont{\normalfont\sc}
 \theorembodyfont{\slshape}
 \theoremheaderfont{\normalfont\sc}
 \theorembodyfont{\slshape}

-\theoremsymbol{$\dagger$}
+\theoremsymbol{}

 \theoremprework{\medskip}
 %\theorempostwork{}
 \theoremseparator{. }
 \theoremprework{\medskip}
 %\theorempostwork{}
 \theoremseparator{. }

-\newtheorem{Proof}{Preuve}%[chapter]
+\newtheorem{Proof}{Preuve}%[]

 
 
 \theoremstyle{plain}
 
 
 \theoremstyle{plain}


@@ -56,6 +56,8 @@
 \newtheorem{Exo}{Exercice}[chapter]
 
 
 \newtheorem{Exo}{Exercice}[chapter]
 
 

+
+

 \theoremstyle{plain}
 %\theoremsymbol{\ensuremath{\clubsuit}}
 \theoremseparator{.}
 \theoremstyle{plain}
 %\theoremsymbol{\ensuremath{\clubsuit}}
 \theoremseparator{.}

diff --git a/rsa.tex b/rsa.tex
index a96d0a218530f7186b0e729625d0bb8491ec39a1..eee81e51080a5fd9ff9e28cb1e32acccbb75d113 100644 (file)
--- a/rsa.tex
+++ b/rsa.tex
@@ -55,71 +55,7 @@ Il s'inspire largement de~\cite{RSA09}
 
 
 
 
 
 

-\section{L'algorithme RSA}
-
-\subsection{Les étapes détaillées de l'algorithme}
-
-On rappelle qu'un système cryptographique à clé publique est
-initialisé par le receveur, c.-à-d. celui qui veut recevoir des messages de
-manière sure. 
-
-\paragraph{Première étape: choix des deux nombres $p$ et $q$.} 
-Le receveur choisit deux grands nombres premiers
-$p$ et $q$ et calcule $n = pq$. Puis il calcule $\varphi(n)$, 
-où $\varphi : \N^* \rightarrow \N^* $ est la \emph{fonction d'Euler} 
-définie par $\varphi(n)$  est le nombre d'entiers dans $\{1, 2, \dots , n -1 \}$ 
-qui sont premiers avec $n$.
-\paragraph{Deuxième  étape: choix de la clé publique.} 
-Le receveur choisit $e \in 
-\{1, \dots , n-1\}$  premier avec $\varphi(n)$.
-La clé publique est la paire $(e,n)$. L'expéditeur
-va s'en servir pour crypter son message à la quatrième étape ci-dessous.
-\paragraph{Troisième  étape: construction de la clé privée.}
-Le receveur calcule l'entier $d \in \{1,\dots, n-1\}$
-tel que le reste de la division de $ed$ par $\varphi(n)$ est 1. 
-Ceci se note aussi $ed \equiv 1 [\varphi(n)]$ qui se lie $ed$ est congru 
-à 1 modulo $\varphi(n)$.
-La paire $(d,n)$ est la clé privée de décryptage. Elle
-est secrète et permet au receveur de décrypter tous les messages reçus
-et cryptés avec $(e,n)$. 
-\paragraph{Quatrième  étape: cryptage du message.}
-L’expéditeur peut crypter tout message écrit sous la forme 
-d'un nombre $m$ appartenant à $\{1, \dots , n-1\}$ et qui est 
-premier avec $n$. 
-Le message codé est le reste $a$ de la division de $m^e$ par $n$. 
-On a donc $m^e \equiv a [n]$, où $a \in \{1, \dots , n - 1\}$.
-\paragraph{Cinquième  étape:  décryptage du message.} 
-Le receveur dispose de $a$ et de sa clé privée $(d,n)$. 
-Pour décrypter $a$, il calcule le reste dans la division par $n$
-de $a^d$ (c.-à-d. $a^d [n]$). 
-Si aucune erreur de calcul n'a été effectuée, c'est le message initial $m$.
-
-
-\subsection{Sur un exemple très petit}
-Le receveur choisit $p=7$, $q=13$.
-\begin{enumerate}
-\item Construire l'ensemble des entiers qui sont premiers avec $n=pq$ 
-  et en déduire que $\varphi(91)=72$.
-\item Montrer que $(29,91)$ est un candidat acceptable de clé publique.
-\item Trouver la clé privée associée.
-\item Montrer que  l'expéditeur a la possibilité de crypter le message $m=59$.
-\item Construire le message crypté $a$ à l'aide de la clé publique.
-\item Décrypter
- le message $a$ à l'aide de la clé privée. Il doit s'agir de $m$. 
-\end{enumerate} 
-
-
-\subsection{Les points clés}
-L'algorithme RSA repose sur plusieurs points clés rencontrés successivement:
-\begin{itemize}
-\item la génération de deux grands nombres premiers $p$ et $q$ ;
-\item la multiplication de grands nombres : $pq$, $ed$,   
-\item l'arithmétique modulaire;
-\item l'algorithme d'Euclide de génération de PGCD et son corollaire de Bézout;
-\item la factorisation, qui tant qu'elle n'est pas réalisable sur des grands nombres, garantit la sécurité du cryptage des données.
-\end{itemize}
-
-\section{Rappels d'arithmétique}
+\section{Rappels d'arithmétique jusqu'au PGCD} 

 
 Soit deux entiers $a$ et $b$ dans $\Z$.
 On dit que $a$ divise $b$ (que l'on note $a | b$)
 
 Soit deux entiers $a$ et $b$ dans $\Z$.
 On dit que $a$ divise $b$ (que l'on note $a | b$)


@@ -132,7 +68,13 @@ $a$ et $b$, noté $a\land b$ est l'entier naturel qui vérifie
 \item Si $d | a$ et $d | b$, alors $d | a\land b$.
 \end{itemize}
 
 \item Si $d | a$ et $d | b$, alors $d | a\land b$.
 \end{itemize}
 

-\subsection{Algorithme d'Euclide de calcul de PGCD}
+
+\begin{Exo}
+Déterminer $550 \land 1540$.
+\end{Exo}
+
+
+%\subsection{Algorithme d'Euclide de calcul de PGCD}

 
 Par définition, le PGCD de $a$ non nul avec
 0 est $a$ (définition raisonnable, car 0
 
 Par définition, le PGCD de $a$ non nul avec
 0 est $a$ (définition raisonnable, car 0


@@ -178,7 +120,6 @@ Donner le code d'un programme qui prend en entrée deux entiers naturels $a$
 et $b$ tels que $a>b \ge 0$ et qui retourne leur PGCD 
 \end{Exo}
 
 et $b$ tels que $a>b \ge 0$ et qui retourne leur PGCD 
 \end{Exo}
 

-\subsection{Les incontournables Bézout et Gau{\ss}}

 
 \begin{Prop}[Identite   de Bézout]
 On considère deux nombres entiers strictement positifs $a$ et $b$. 
 
 \begin{Prop}[Identite   de Bézout]
 On considère deux nombres entiers strictement positifs $a$ et $b$. 


@@ -214,6 +155,16 @@ r_{n}  & = & r_{n-2} - r_{n-1} \times q_{n}  \nonumber \\
 \end{eqnarray}
 \end{Proof}
 
 \end{eqnarray}
 \end{Proof}
 

+\begin{Exo}
+Montrer qu'il existe $x$ et $y$ tels que 
+$29x + 72y=1$ puis trouver une valeur pour  $x$ et $y$.
+\end{Exo}
+
+
+\begin{Exo}
+Montrer que les propriétés $ a \land m = 1 $
+et $ b \land m = 1 $ impliquent $ ab \land m = 1 $.
+\end{Exo}

 
 
 \begin{Def}[Nombres premiers entre eux]
 
 
 \begin{Def}[Nombres premiers entre eux]


@@ -221,7 +172,108 @@ Les deux entiers relatifs $a$ et $b$ sont premiers entre eux si
 leur plus grand commun diviseur est égal à 1.
 \end{Def}
 
 leur plus grand commun diviseur est égal à 1.
 \end{Def}
 

+\begin{Exo}
+Montrer que 55 et 21 sont premiers entre eux.
+\end{Exo}
+
+
+
+
+
+
+
+\section{L'algorithme RSA}
+
+\subsection{Les étapes détaillées de l'algorithme}
+
+On rappelle qu'un système cryptographique à clé publique est
+initialisé par le receveur, c.-à-d. celui qui veut recevoir des messages de
+manière sure. 
+
+\paragraph{Première étape: choix des deux nombres $p$ et $q$.} 
+Le receveur choisit deux grands nombres premiers
+$p$ et $q$ et calcule $n = pq$. Puis il calcule $\varphi(n)$, 
+où $\varphi : \N^* \rightarrow \N^* $ est la \emph{fonction d'Euler} 
+L'entier $\varphi(n)$  est le nombre d'entiers 
+dans $\{1, 2, \dots , n -1 \}$ qui sont premiers avec $n$.
+
+\begin{Exo}
+Le receveur choisit $p=7$, $q=13$.
+Construire l'ensemble des entiers qui sont premiers avec $n=pq$ 
+et en déduire que $\varphi(91)=72$.
+\end{Exo}
+
+
+\paragraph{Deuxième  étape: choix de la clé publique.} 
+Le receveur choisit $e \in 
+\{1, \dots , n-1\}$  premier avec $\varphi(n)$.
+La clé publique est la paire $(e,n)$. 
+Chaque expéditeur
+va s'en servir pour crypter son message à destination de ce receveur.
+Le cryptage est détaillé 
+ à la quatrième étape ci-dessous.

 
 

+\begin{Exo}
+Montrer que $(29,91)$ est un candidat acceptable de clé publique.
+\end{Exo}
+
+\paragraph{Troisième  étape: construction de la clé privée.}
+Le receveur calcule l'entier $d \in \{1,\dots, n-1\}$
+tel que le reste de la division de $ed$ par $\varphi(n)$ est 1. 
+Ceci se note aussi $ed \equiv 1 [\varphi(n)]$ qui se lie $ed$ est congru 
+à 1 modulo $\varphi(n)$.
+La paire $(d,n)$ est la clé privée de décryptage. 
+Elle est secrète et permet au receveur de décrypter tous les messages reçus
+et cryptés avec $(e,n)$. 
+
+\begin{Exo}
+ Trouver la clé privée associée.
+\end{Exo}
+
+
+\paragraph{Quatrième  étape: cryptage du message.}
+L’expéditeur peut crypter tout message écrit sous la forme 
+d'un nombre $m$ appartenant à $\{1, \dots , n-1\}$ et qui est 
+premier avec $n$. 
+Le message codé est le reste $a$ de la division de $m^e$ par $n$. 
+On a donc $m^e \equiv a [n]$, où $a \in \{1, \dots , n - 1\}$.
+
+\begin{Exo}
+\begin{enumerate}
+\item Montrer que  l'expéditeur a la possibilité de crypter le message $m=59$.
+\item Construire le message crypté $a$ à l'aide de la clé publique.
+\end{enumerate}
+\end{Exo}
+
+\paragraph{Cinquième  étape:  décryptage du message.} 
+Le receveur dispose de $a$ et de sa clé privée $(d,n)$. 
+Pour décrypter $a$, il calcule le reste dans la division par $n$
+de $a^d$ (c.-à-d. $a^d [n]$). 
+Si aucune erreur de calcul n'a été effectuée, c'est le message initial $m$.
+
+
+\begin{Exo}
+Décrypter
+ le message $a$ à l'aide de la clé privée. Il doit s'agir de $m$. 
+\end{Exo}
+
+
+\subsection{Les points clés}
+L'algorithme RSA repose sur plusieurs points clés rencontrés successivement:
+\begin{itemize}
+\item la génération de deux grands nombres premiers $p$ et $q$ ;
+\item la multiplication de grands nombres : $pq$, $ed$,   
+\item l'arithmétique modulaire;
+\item l'algorithme d'Euclide de génération de PGCD et son corollaire de Bézout;
+\item la factorisation, qui tant qu'elle n'est pas réalisable sur des grands nombres, garantit la sécurité du cryptage des données.
+\end{itemize}
+
+
+
+%\subsection{L'algorithme de RSA est correct}
+
+\section{Les incontournables théorèmes de Bézout et de 
+  Gau{\ss}}

 
 \begin{Prop}[Théorème de Bézout]
 Deux entiers strictement positifs 
 
 \begin{Prop}[Théorème de Bézout]
 Deux entiers strictement positifs 


@@ -248,8 +300,9 @@ Si $a$ divise le produit $bc$
 et s'il est premier avec $b$, alors il divise $c$.
 \end{Prop}
 
 et s'il est premier avec $b$, alors il divise $c$.
 \end{Prop}
 

+

 \begin{Exo}
 \begin{Exo}

-Faire la preuve de ce théorème
+Faire la preuve du  théorème de Gau{\ss}.

 \end{Exo}
 
 \begin{Prop}[Fonction d'Euler]
 \end{Exo}
 
 \begin{Prop}[Fonction d'Euler]


@@ -306,42 +359,6 @@ d'inconnues $x$ et $y$.
 \end{Exo}
 
 
 \end{Exo}
 
 

-\begin{Exo}[Sujet du bac S Liban 2005]
-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$.}
-\begin{enumerate}
-\item  On considère l’équation $(E)$ : $109x-226y=1$ où $x$ et $y$
-  sont des entiers relatifs.
-\begin{enumerate}
-\item  Déterminer $109\land 226$. 
-  Que peut-on en conclure pour l'équation $(E)$? 
-\item  Montrer que l'ensemble des solutions de $(E)$  
-  est l'ensemble des couples de la forme 
-  $(141+226k ;68+109k)$, où $k$ appartient à $\Z$.
-  En déduire qu'il existe un unique entier naturel non nul $d$ 
-  inférieur ou égal à 226 et un unique entier naturel non nul $e$ tels que
-  $109d =1+226 e$ (on précisera les valeurs des entiers $d$ et $e$).
-\end{enumerate}
-\item Démontrer que 227 est un nombre premier.
-\item  On note $A=\{0,1,2,\dots,226\}$. On considère les deux fonctions 
-  $f$ et $g$ de $A$ dans $A$ définies de la manière suivante: 
-\begin{itemize}
-\item  A tout entier $a\in A$, $f$ associe le reste de
-  la division euclidienne de $a^{109}$ par 227.
-\item A tout entier $a\in A$, $g$ associe le reste de la
-  division euclidienne de $a^{141}$ par 227.
-\end{itemize}
-\begin{enumerate}
-\item Vérifier que $g(f(0))=0$ .
-\item Montrer que, quel que soit l'entier non nul $a$ de $A$ , $a^{226}-1$ est multiple de 227.
-\item En déduire que, quel que soit l'entier non nul $a$ de $A$, 
-$g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
-\end{enumerate}
-\end{enumerate}
-\end{Exo}

 
 
 
 
 
 


@@ -429,6 +446,13 @@ $261x +2$ soit multiple de 305.
 \end{enumerate}
 \end{Exo}
 
 \end{enumerate}
 \end{Exo}
 

+\begin{Exo}
+Soit $p$ un nombre premier tel que $p \equiv 3 [4]$. 
+Soit $a$  un entier qui est un carré, modulo $p$:
+il existe $b$ tel que $a \equiv b^2 [p]$.
+Montrer que 
+$a^{(p+1)/4}$ est une racine carré de $a$, modulo $p$.  
+\end{Exo}

 
 
 
 
 
 


@@ -528,6 +552,46 @@ $p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ est premier avec  $a$ d'après le
 hypothèses. D'après le théorème de Gau{\ss}, $p$ divise $a^{p-1}-1$.
 \end{Proof}
 
 hypothèses. D'après le théorème de Gau{\ss}, $p$ divise $a^{p-1}-1$.
 \end{Proof}
 

+
+\begin{Exo}[Sujet du bac S Liban 2005]
+% 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$.}
+\begin{enumerate}
+\item  On considère l’équation $(E)$ : $109x-226y=1$ où $x$ et $y$
+  sont des entiers relatifs.
+\begin{enumerate}
+\item  Déterminer $109\land 226$. 
+  Que peut-on en conclure pour l'équation $(E)$? 
+\item  Montrer que l'ensemble des solutions de $(E)$  
+  est l'ensemble des couples de la forme 
+  $(141+226k ;68+109k)$, où $k$ appartient à $\Z$.
+  En déduire qu'il existe un unique entier naturel non nul $d$ 
+  inférieur ou égal à 226 et un unique entier naturel non nul $e$ tels que
+  $109d =1+226 e$ (on précisera les valeurs des entiers $d$ et $e$).
+\end{enumerate}
+\item Démontrer que 227 est un nombre premier.
+\item  On note $A=\{0,1,2,\dots,226\}$. On considère les deux fonctions 
+  $f$ et $g$ de $A$ dans $A$ définies de la manière suivante: 
+\begin{itemize}
+\item  A tout entier $a\in A$, $f$ associe le reste de
+  la division euclidienne de $a^{109}$ par 227.
+\item A tout entier $a\in A$, $g$ associe le reste de la
+  division euclidienne de $a^{141}$ par 227.
+\end{itemize}
+\begin{enumerate}
+\item Vérifier que $g(f(0))=0$ .
+\item Montrer que, quel que soit l'entier non nul $a$ de $A$ , $a^{226}-1$ est multiple de 227.
+\item En déduire que, quel que soit l'entier non nul $a$ de $A$, 
+$g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
+\end{enumerate}
+\end{enumerate}
+\end{Exo}
+
+
+

 \subsection{Puissance de grands nombres}
 
 \begin{Exp}
 \subsection{Puissance de grands nombres}
 
 \begin{Exp}


@@ -551,13 +615,13 @@ Calculer $2^{500} [13]$ et $26^{1000} [17]$.
 \end{Exo}
 
 
 \end{Exo}
 
 

-\begin{Exo}
-Montrer que si l'entier naturel $n$ est premier alors
-$$(x +1)^n \equiv x^n +1[n].$$
+% \begin{Exo}
+% Montrer que si l'entier naturel $n$ est premier alors
+% $$(x +1)^n \equiv x^n +1[n].$$

 
 

-On a même l'équivalence, cependant, l'autre sens est plus technique à démontrer.
+% On a même l'équivalence, cependant, l'autre sens est plus technique à démontrer.

 
 

-\end{Exo}
+% \end{Exo}

 
 
 
 
 
 


@@ -585,7 +649,7 @@ $N$  qui sont premiers.
 La fonction $\pi:\N \rightarrow \N$  associe 
 à chaque nombre $N$ le nombre d'entiers inférieurs ou égaux à $N$ qui sont 
 premiers, soit $\pi(N) = |\{p \le N | p \textrm{ premier}\}|$.
 La fonction $\pi:\N \rightarrow \N$  associe 
 à chaque nombre $N$ le nombre d'entiers inférieurs ou égaux à $N$ qui sont 
 premiers, soit $\pi(N) = |\{p \le N | p \textrm{ premier}\}|$.

-Lorsque $n$ est grand, on a:
+Lorsque $N$ est grand, on a:

 \begin{eqnarray}
 \pi(N) &\approx& \dfrac{N}{\ln(N)}
 \end{eqnarray}
 \begin{eqnarray}
 \pi(N) &\approx& \dfrac{N}{\ln(N)}
 \end{eqnarray}


@@ -594,7 +658,7 @@ La preuve de ce théorème est d'un niveau très avancé et n'est pas reproduite
 ici.
 
 Pour obtenir un  entier de 100 chiffres, il suffit de considérer 
 ici.
 
 Pour obtenir un  entier de 100 chiffres, il suffit de considérer 

-$N= 10^{100}$. Si on choisit au hasard un nombre $n$ dans $\N_{N}^{*}$,
+$N= 10^{100}$. Si on choisit au hasard un nombre dans $\N_{N}^{*}$,

 la probabilité qu'il soit premier est: 
 \begin{eqnarray*}
 \textrm{Prob}(n \textrm{ premier}) &\approx&
 la probabilité qu'il soit premier est: 
 \begin{eqnarray*}
 \textrm{Prob}(n \textrm{ premier}) &\approx&


@@ -672,15 +736,15 @@ il suffit de vérifier  qu'il n'est pas multiple d'un nombre premiers inférieur
 
 \subsubsection{Tests probabilistes}
 
 
 \subsubsection{Tests probabilistes}
 

-\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}
- \forall a\in \N \forall p \in \N (   p \in \Prem \textrm{ et }   a \not\equiv  0[p] 
-  \Rightarrow a^{p-1}\equiv 1 [p]).
-\label{petittheremeFermat}
-\end{equation}
-\end{Prop}
+% \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}
+%  \forall a\in \N \forall p \in \N (   p \in \Prem \textrm{ et }   a \not\equiv  0[p] 
+%   \Rightarrow a^{p-1}\equiv 1 [p]).
+% \label{petittheremeFermat}
+% \end{equation}
+% \end{Prop}

 
 
 \paragraph{Test de Fermat.}
 
 
 \paragraph{Test de Fermat.}


@@ -699,7 +763,7 @@ pourtant $341 =  11 \times 31$.
 
 \begin{Exo}
 Donner le code de la fonction \verb+testPrimaliteFermat(n,t)+ qui retourne 
 
 \begin{Exo}
 Donner le code de la fonction \verb+testPrimaliteFermat(n,t)+ qui retourne 

-\verb+True+ si \verb+t+ evaluations de $\texttt{a}^{\texttt{p}-1}$ on retourné $ 1 [\texttt{p}]$ 
+\verb+True+ si \verb+t+ evaluations de $\texttt{a}^{\texttt{n}-1}$ ont retourné $ 1 [\texttt{n}]$ 

 pour un $a \in \N_{n-1}^{*}$ et \verb+False+ sinon.
 \end{Exo}
 
 pour un $a \in \N_{n-1}^{*}$ et \verb+False+ sinon.
 \end{Exo}
 


@@ -742,15 +806,86 @@ sous la forme de $p\times q$ si ces deux derniers nombres ont été mal choisis.
 
 
 \begin{Exo}
 
 
 \begin{Exo}

-On considère que l'étape 1 de l'algorithme RSA a généré deux nombre premiers $p$ et $q$ tels que $p>q$. On définit  $t = \frac{p+q}{2}$ et $s = \frac{p-q}{2}$.
+On considère que l'étape 1 de l'algorithme RSA a généré deux nombre premiers $p$ et $q$ proches tels que $p>q$. On définit  $t = \frac{p+q}{2}$ et $s = \frac{p-q}{2}$.

 Montrer que
 \begin{enumerate}
 \item le produit $n = pq = t^2 - s^2$;
 \item l'entier $t$ est légèrement supérieur à la racine carrée de $n$ et que $s $ est petit;
 \item l'on peut utiliser ces informations pour factoriser $n$ c.-à-d. retrouver $p$ et $q$;
 Montrer que
 \begin{enumerate}
 \item le produit $n = pq = t^2 - s^2$;
 \item l'entier $t$ est légèrement supérieur à la racine carrée de $n$ et que $s $ est petit;
 \item l'on peut utiliser ces informations pour factoriser $n$ c.-à-d. retrouver $p$ et $q$;

-\item Factoriser 9623827 et  343570291. % res=2953*3259     res = 17729*19379
+\item Factoriser 896861 et  318040531. % res=2953*3037     res = 17729*17939
+\item Factoriser 9623827 et 343570291. % res=(3259, 2953)     res = (19379, 17729)

 \end{enumerate}
 \end{Exo}
 
 \end{enumerate}
 \end{Exo}
 

+\begin{TP}
+L'objectif de ce TP est d'implanter toute la démarche RSA 
+avec les éléments vus en TD. 
+% Tout ceci est à synthétiser dans un document 
+% libreoffice à renvoyer à l'adresse \url{couchot@femto-st.fr} avec pour sujet 
+% RSA-NOM1-NOM2-TDX.
+\begin{enumerate}
+\item Quel est le plus petit nombre à trois chiffres? 
+  Quel est le plus grand nombre à trois chiffres? 
+  Comment générer aléatoirement un nombre qui a trois chiffres en utilisant 
+  \verb+randint+?
+\item Même question que la question précédente, en remplaçant \og trois\fg{}
+  par $M$.  
+\item On a vu qu'un nombre se terminant par 0,2,4,5,6,8 n'est jamais premier.
+  Comment générer un nombre qui a $N$ chiffres, dont le dernier chiffre 
+  n'est pas  dans la liste précédente.
+\item Pour affirmer qu'un nombre de 100 chiffres 
+  est premier, on invoquera le test de Miller-Rabin avec 50
+  valeurs testées  différentes $a$. Si toutes retournent qu'il est 
+  probablement premier, on considérera qu'il l'est.
+  Construire la fonction \verb+genereUnNombrePremier(N)+ qui retourne 
+  un nombre probablement premier selon cette méthode.
+  %Copier-coller cette fonction dans votre synthèse.
+\item A l'aide de l'agorithme précédent, générer deux nombres premiers 
+  $p$ et $q$ de 100 chiffres.
+  %Copier et coller ces deux nombres dans votre synthèse.
+  Calculer $n=pq$ puis \verb+phi+ telle 
+  que \verb+phi=(p-1)*(q-1)+.
+
+\item Contruire la partie $e$ de la clé publique $(e,n)$
+  comme un nombre premier de trente chiffres par exemple. 
+  Si elle est première avec \verb+phi+, c'est une bonne clé, sinon on 
+  regénere un nombre premier de trente chiffres.
+  %Copier et coller $e$ dans votre synthèse.
+
+\item Donner le code la fonction \verb+bezout(+$a$,$b$\verb+)+ 
+qui retourne $x$ et $y$ tels que $x.a + y.b = a \land b$.
+
+%  \begin{verbatim}
+% def bezout(a,b):
+%   if b==0: return [1,0]
+%   else:
+%     uv= bezout(b,a%b)
+%     return [uv[1],uv[0]-uv[1]*(a/b)]
+% \end{verbatim}
+
+Se servir de cette fonction pour générer la partie $d$ de 
+la clé privée $(d,n)$. Attention, faire en sorte que $0 \le d \le$\verb+phi+.
+%Copier-coller les instructions permettant d'obtenir $d$.
+%Copier-coller la valeur de $d$.
+
+\item Chiffrer à l'aide de la clé publique $(e,n)$
+  le message $m=3402752281514000316845$  
+  qui est un numéro de carte bancaire comprenant les 16 chiffres, 
+  la date de validité et le code de sécurité. Le mesage chiffré est $a$.
+  %Copier-coller l'instructions permettant d'obtenir $a$.
+  %Copier-coller la valeur de $a$.
+  
+
+\item Déchiffrer $a$ à l'aide de la clé privée. 
+  Vérifier que vous obtenez bien $m$ à nouveau.
+  %Copier-coller l'instructions permettant de déchiffrer $a$.
+\end{enumerate} 
+
+
+ 
+\end{TP}
+
+
+

 % \section{Conclusion}
 % cf SMATH paragraphe applications p 223.
\ No newline at end of file
 % \section{Conclusion}
 % cf SMATH paragraphe applications p 223.
\ No newline at end of file

diff --git a/tps/AlgoFermatFacto.py~ b/tps/AlgoFermatFacto.py~
deleted file mode 100644 (file)
index 685f2a7..0000000
--- a/tps/AlgoFermatFacto.py~
+++ /dev/null
@@ -1,28 +0,0 @@
-import math as m
-
-def estUnCarre(k):
-    return (int(m.sqrt(k)))**2 == k
-
-def facto(n):
-    t= int(m.sqrt(n))+1
-    sp = t**2 - n 
-    while not estUnCarre(sp):
-        t += 1
-        sp = t**2 -n
-        print "+",
-    return(int(t+m.sqrt(sp)),int(t-m.sqrt(sp)))
-    
-
-
-
-
-print facto(5959)
-print facto(2953*3037)
-print facto(6197*6299)
-print facto(2953*3037)        
-print facto(17729*17939)
-
-
-print facto(9623827)
-print facto(343570291)
-    

diff --git a/tps/testProbabilite.py~ b/tps/testProbabilite.py~
deleted file mode 100644 (file)
index 66edb82..0000000
--- a/tps/testProbabilite.py~
+++ /dev/null
@@ -1,125 +0,0 @@
-from random import *
-
-
-
-testes = []
-
-def testPrimaliteFermat(n,t):
-    global testes
-    j = 0 
-    ret = True
-    while j < t and ret :
-        print j
-        # choix de a 
-        a = randint(1,n-1)
-        while a in testes:
-            a = randint(1,n-1)
-        #calcul de a^(n-1) [n]
-        #if a**(n-1) % n != 1 :
-        if pow(a,n-1,n) != 1 :
-            ret = False
-        else : 
-            j+= 1
-            testes +=[a]
-    return ret
-
-
-
-
-
-
-
-def testPrimaliteMillerRabin(n,t):
-    global testes 
-    if n % 2 == 0:
-        return False
-    
-    # ecrire  n-1 comme 2**s * d
-    s,d = 0, n-1
-    while d % 2 == 0 :
-        s +=1
-        d /= 2 
-    #testes = []
-    j = 0 
-    ret = True
-    while j < t and ret :
-        # choix de a 
-        a = randint(1,n-1)
-        while a in testes:
-            a = randint(1,n-1)
-        # calcul de a^(d) [n]
-        if pow(a, d, n) != 1:
-            ret = False
-            r=0
-            while r < s and not ret:
-                if pow(a, 2**r * d, n) ==  n-1:
-                    ret= True
-                else :
-                    r+=1
-        j+=1
-        #print j
-        testes +=[a]
-
-    return ret
-
-
-n=651693055693681
-#n= 39341 
-#n=561
-
-#print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500)
-#print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,30)
-
-
-def genereUnNombrePremier(nbChiffre):
-    estPremier=False
-    compteur, r = 0, 0 
-    mini = 10**(nbChiffre-2)
-    maxi = 10**(nbChiffre-1)-1
-    chiffreFinal=[1,3,7,9]
-    while (not estPremier):
-        r = randint(mini,maxi)*10
-        r += chiffreFinal[randint(0,3)]
-        #print r
-        compteur += 1
-        if testPrimaliteMillerRabin(r,50):
-            estPremier = True
-    return (r,compteur)
-
-nbit,l=0,100
-for k in range(l):
-    (r,n)= genereUnNombrePremier(100)
-    nbit += n
-    print r
-print float(nbit)/l
-
-"""
-
-
-
-
-
-
-
-
-
-
-
-
-    
-
-
-
-t = 50
-n = 393413 #premier
-n=651693055693681
-#n = 393417 #premier
-n=9623827 #et  343570291. % res=2953*3259     res = 17729*19379
-print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,t)
-print "probabilite d'etre premier (MILLER-RABIN)", testPrimaliteMillerRabin(n,t)
-
-    
-    
-
-"""
-    

diff --git a/tps/testProbabiliteAvecGeneration.py~ b/tps/testProbabiliteAvecGeneration.py~
deleted file mode 100644 (file)
index 66edb82..0000000
--- a/tps/testProbabiliteAvecGeneration.py~
+++ /dev/null
@@ -1,125 +0,0 @@
-from random import *
-
-
-
-testes = []
-
-def testPrimaliteFermat(n,t):
-    global testes
-    j = 0 
-    ret = True
-    while j < t and ret :
-        print j
-        # choix de a 
-        a = randint(1,n-1)
-        while a in testes:
-            a = randint(1,n-1)
-        #calcul de a^(n-1) [n]
-        #if a**(n-1) % n != 1 :
-        if pow(a,n-1,n) != 1 :
-            ret = False
-        else : 
-            j+= 1
-            testes +=[a]
-    return ret
-
-
-
-
-
-
-
-def testPrimaliteMillerRabin(n,t):
-    global testes 
-    if n % 2 == 0:
-        return False
-    
-    # ecrire  n-1 comme 2**s * d
-    s,d = 0, n-1
-    while d % 2 == 0 :
-        s +=1
-        d /= 2 
-    #testes = []
-    j = 0 
-    ret = True
-    while j < t and ret :
-        # choix de a 
-        a = randint(1,n-1)
-        while a in testes:
-            a = randint(1,n-1)
-        # calcul de a^(d) [n]
-        if pow(a, d, n) != 1:
-            ret = False
-            r=0
-            while r < s and not ret:
-                if pow(a, 2**r * d, n) ==  n-1:
-                    ret= True
-                else :
-                    r+=1
-        j+=1
-        #print j
-        testes +=[a]
-
-    return ret
-
-
-n=651693055693681
-#n= 39341 
-#n=561
-
-#print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,500)
-#print "probabilite d'etre premier (Miller Rabin)", testPrimaliteMillerRabin(n,30)
-
-
-def genereUnNombrePremier(nbChiffre):
-    estPremier=False
-    compteur, r = 0, 0 
-    mini = 10**(nbChiffre-2)
-    maxi = 10**(nbChiffre-1)-1
-    chiffreFinal=[1,3,7,9]
-    while (not estPremier):
-        r = randint(mini,maxi)*10
-        r += chiffreFinal[randint(0,3)]
-        #print r
-        compteur += 1
-        if testPrimaliteMillerRabin(r,50):
-            estPremier = True
-    return (r,compteur)
-
-nbit,l=0,100
-for k in range(l):
-    (r,n)= genereUnNombrePremier(100)
-    nbit += n
-    print r
-print float(nbit)/l
-
-"""
-
-
-
-
-
-
-
-
-
-
-
-
-    
-
-
-
-t = 50
-n = 393413 #premier
-n=651693055693681
-#n = 393417 #premier
-n=9623827 #et  343570291. % res=2953*3259     res = 17729*19379
-print "probabilite d'etre premier (FERMAT)", testPrimaliteFermat(n,t)
-print "probabilite d'etre premier (MILLER-RABIN)", testPrimaliteMillerRabin(n,t)
-
-    
-    
-
-"""
-