More exercices (notably the p-1 method).

1 files changed, 125 insertions, 30 deletions

diff --git a/controle-20081202.tex b/controle-20081202.tex
index a0b3771..44a0052 100644
--- a/controle-20081202.tex
+++ b/controle-20081202.tex
@@ -39,9 +39,19 @@
 
 \textbf{Consignes :}
 
+Les exercices sont complètement indépendants.  Ils pourront être
+traités dans un ordre quelconque, mais on demande de faire apparaître
+de façon très visible dans les copies où commence chaque exercice.  À
+l'intérieur d'un exercice, les questions se suivent normalement dans
+un ordre logique, et il est recommandé de les traiter dans cet ordre.
+
 L'usage de tous les documents (notes de cours manuscrites ou
-imprimées, livres) est autorisée.  L'usage des calculatrices
-électroniques n'est pas autorisée.
+imprimées, livres) est autorisée.
+
+L'usage des calculatrices électroniques n'est pas autorisée.
+(Certains exercices peuvent apparaître calculatoires, mais les calculs
+sont toujours faisables à la main en un temps raisonnable, parfois au
+prix de quelques astuces.)
 
 \newpage
 
@@ -51,6 +61,20 @@ imprimées, livres) est autorisée.  L'usage des calculatrices
 
 \exercice
 
+Les deux questions suivantes sont indépendantes.
+
+(1) Montrer que $a^{31} \equiv a \pmod{341}$ pour tout $a \in
+\mathbb{Z}$ (note : on a $341 = 11\times 31$).
+
+(2) Pourquoi a-t-on $a^{32} \equiv 1 \pmod{128}$ pour tout $a$ impair
+(note : $128 = 2^7$) ?
+
+%
+%
+%
+
+\exercice
+
 Le calendrier religieux maya (ou Tzolkin) est la combinaison de deux
 cycles indépendant, l'un de $13$ jours numérotés de 1 à 13, l'autre de
 $20$ jours portant des noms de dieux (dans l'ordre : « Ahau »,
@@ -116,48 +140,119 @@ Par $990$ ?
 
 \exercice
 
-Montrer que $a^{31} \equiv a \pmod{341}$ pour tout $a \in \mathbb{Z}$
-(note : on a $341 = 11\times 31$).
-
-%
-%
-%
-
-\exercice
-
-Montrer que tout $x \in \mathbb{F}_{32}^\times$ est primitif.  Combien
-d'éléments de $\mathbb{F}_{64}^\times$ sont primitifs ?
-
-%
-%
-%
-
-\exercice
-
 Une conjecture affirme que pour tout entier $n$ il existe $n' \neq n$
 tel que $\varphi(n') = \varphi(n)$ (où $\varphi$ désigne la fonction
 indicatrice d'Euler).  On va voir qu'on peut montrer cette conjecture
 au moins pour les petites valeurs de $n$.
 
-(1) Si $n$ est impair, montrer que $\varphi(2n) = \varphi(n)$.
+(1a) Si $n$ est impair, montrer que $\varphi(2n) = \varphi(n)$.
 
-(2) Si $n$ est pair mais non multiple de $4$, montrer que
+(1b) Si $n$ est pair mais non multiple de $4$, montrer que
 $\varphi(\frac{1}{2}n) = \varphi(n)$.
 
-(3) Si $n$ est multiple de $4$ mais non de $12$, montrer que
+(1c) Si $n$ est multiple de $4$ mais non de $12$, montrer que
 $\varphi(\frac{3}{2}n) = \varphi(n)$.
 
-(4) Si $n$ est multiple de $12$ mais non de $36$, montrer
+(1d) Si $n$ est multiple de $12$ mais non de $36$, montrer
 que $\varphi(\frac{2}{3}n) = \varphi(n)$.
 
-(5) Si $n$ est multiple de $36$ mais non de $7\times 36$, montrer
-que $\varphi(\frac{7}{6}n) = \varphi(n)$.
+(1e) Si $n$ est multiple de $36$ mais non de $7\times 36 = 252$,
+montrer que $\varphi(\frac{7}{6}n) = \varphi(n)$.
+
+(1f) Si $n$ est multiple de $7\times 36 = 252$ mais non de $7^2\times
+36 = 1764$, montrer que $\varphi(\frac{6}{7}n) = \varphi(n)$.
+
+(2) En continuant selon la même logique, montrer que la conjecture
+énoncée plus haut est valable lorsque $n$ n'est pas multiple de
+$(6\times 7 \times 43)^2$.
+
+(3) Si $n$ est multiple de $(6\times 7 \times 43)^2$ mais ni de $27$
+ni de $13$, montrer que $\varphi(\frac{13}{18}n) = \varphi(n)$.
+
+(4) Sachant que $(6\times 7 \times 43)^2 \geq 3\times 10^6$, jusqu'à
+combien les questions précédentes permettent-elles d'affirmer la
+véracité de la conjecture ?
+
+%
+%
+%
+
+\exercice
 
-(6) Si $n$ est multiple de $7\times 36$ mais non de $7^2\times 36$,
-montrer que $\varphi(\frac{6}{7}n) = \varphi(n)$.
+Cet exercice décrit le principe l'algorithme de factorisation
+« $p-1$ » de Pollard.
+
+\emph{Définition :} On dit qu'un entier naturel $m$ est
+     « $B$-friable » (pour $B$ un entier naturel) lorsque tout facteur
+     premier $\ell$ de $m$ est $\leq B$.  (Par exemple, $720$ est
+     $5$-friable.)
+
+(1) Soit $p$ un nombre premier tel que $p-1$ soit $B$-friable (pour
+une certaine borne $B$).  Soient $\ell_1,\ldots,\ell_k$ les nombres
+premiers $\leq B$.  Partant de $a \in
+(\mathbb{Z}/p\mathbb{Z})^\times$, on effectue les opérations
+suivantes : pour $i$ allant de $1$ à $k$, on remplace $a$ par
+$a^{\ell_i^{r_i}}$ (ce calcul étant fait dans
+$\mathbb{Z}/p\mathbb{Z}$), où $r_i$ est un entier supérieur ou égal à
+$\log(p)/\log(\ell_i)$.  Quel est le résultat obtenu (autrement dit,
+que vaut $a$ après ces différentes opérations) ?  \emph{Indication :}
+montrer qu'on a élevé $a$ à une puissance d'exposant multiple
+de $p-1$.
+
+\smallskip
+
+On suppose maintenant que $N$ est un entier non premier à factoriser,
+et on espère qu'un de ses facteurs premiers $p$ est tel que $p-1$ soit
+$B$-friable avec $B$ assez petit.  (Naturellement, on ne sait pas ce
+que vaut $p$ !  On cherche justement à le calculer ou, du moins, à
+trouver une factorisation non triviale $N = d d'$ avec $d,d'>1$.)
+
+L'algorithme $p-1$ de Pollard effectue le calcul suivant, en partant
+d'un nombre $N$ à factoriser et d'une borne $B$ de friabilité
+(typiquement de l'ordre de $10^6$) :
+\begin{itemize}
+\item tirer au hasard un entier $a$ entre $2$ et $N-2$ ;
+\item calculer $\pgcd(a,N)$ : s'il est $>1$, terminer : ($*$) on a
+  trouvé une factorisation non triviale de $N$ ;
+\item énumérer les nombres premiers $\ell_1,\ldots,\ell_k$ inférieurs
+  ou égaux à $B$ ;
+\item pour $i$ allant de $1$ à $k$ :
+\begin{itemize}
+\item soit $r \geq \log(N)/\log(\ell_i)$ entier,
+\item faire $a \leftarrow a^{\ell_i^r}$ dans $\mathbb{Z}/N\mathbb{Z}$ ;
+\end{itemize}
+\item calculer $d = \pgcd(a-1,N)$ ;
+\item si $1<d<N$, terminer : ($*$) on a trouvé une factorisation non
+  triviale de $N$ ;
+\item si $d=1$, terminer avec l'erreur suivante : ($\dagger$) il
+  n'existe aucun facteur $p$ de $N$ tel que $p-1$ soit $B$-friable (on
+  peut essayer d'augmenter $B$ et de recommencer) ;
+\item si $d=N$, terminer avec l'erreur suivante : ($\ddagger$) on n'a
+  pas eu de chance (on peut recommencer pour un $a$ différent) ou bien
+  tous les facteurs $p$ de $N$ sont tels que $p-1$ soit $B$-friable
+  (on peut recommancer avec un $B$ plus petit).
+\end{itemize}
+
+\smallskip
+
+(2a) Expliquer les affirmations ($*$) « on a trouvé une factorisation
+  non triviale » de l'algorithme.
+
+(2b) Expliquer l'affirmation ($\dagger$) « il n'existe aucun facteur
+  $p$ de $N$ tel que $p-1$ soit $B$-friable ».  \emph{Indication :}
+utiliser la question (1).
+
+(2c) Proposer un exemple de situation pouvant conduire au dernier
+cas ($\ddagger$).
 
-(7) Montrer la vérité de la conjecture énoncée plus haut lorsque $n <
-(6\times 7 \times 43)^2$.
+%
+%
+%
+
+\exercice
+
+Montrer que tout $x \in \mathbb{F}_{32}^\times$ est primitif.  Combien
+d'éléments de $\mathbb{F}_{64}^\times$ sont primitifs ?
 
 %
 %