From: couchot Date: Wed, 26 Aug 2015 09:31:17 +0000 (+0200) Subject: ajout de qques exos X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/modelisationMathS3.git/commitdiff_plain/HEAD ajout de qques exos --- diff --git a/main.tex b/main.tex index 244a854..22badb0 100755 --- a/main.tex +++ b/main.tex @@ -38,14 +38,14 @@ -\theoremstyle{plain} +\theoremstyle{nonumberplain} \theoremheaderfont{\normalfont\sc} \theorembodyfont{\slshape} -\theoremsymbol{$\dagger$} +\theoremsymbol{} \theoremprework{\medskip} %\theorempostwork{} \theoremseparator{. } -\newtheorem{Proof}{Preuve}%[chapter] +\newtheorem{Proof}{Preuve}%[] \theoremstyle{plain} @@ -56,6 +56,8 @@ \newtheorem{Exo}{Exercice}[chapter] + + \theoremstyle{plain} %\theoremsymbol{\ensuremath{\clubsuit}} \theoremseparator{.} diff --git a/rsa.tex b/rsa.tex index a96d0a2..eee81e5 100644 --- 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$) @@ -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} -\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 @@ -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} -\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$. @@ -214,6 +155,16 @@ r_{n} & = & r_{n-2} - r_{n-1} \times q_{n} \nonumber \\ \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] @@ -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} +\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 @@ -248,8 +300,9 @@ Si $a$ divise le produit $bc$ et s'il est premier avec $b$, alors il divise $c$. \end{Prop} + \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] @@ -306,42 +359,6 @@ d'inconnues $x$ et $y$. \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} +\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} + +\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} @@ -551,13 +615,13 @@ Calculer $2^{500} [13]$ et $26^{1000} [17]$. \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}\}|$. -Lorsque $n$ est grand, on a: +Lorsque $N$ est grand, on a: \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 -$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& @@ -672,15 +736,15 @@ il suffit de vérifier qu'il n'est pas multiple d'un nombre premiers inférieur \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.} @@ -699,7 +763,7 @@ pourtant $341 = 11 \times 31$. \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} @@ -742,15 +806,86 @@ sous la forme de $p\times q$ si ces deux derniers nombres ont été mal choisis. \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$; -\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} +\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 diff --git a/tps/AlgoFermatFacto.py~ b/tps/AlgoFermatFacto.py~ deleted file mode 100644 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 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 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) - - - - -""" -