summaryrefslogtreecommitdiffstats
path: root/controle-20081202.tex
diff options
context:
space:
mode:
authordavid <david>2008-11-27 01:26:21 +0000
committerdavid <david>2008-11-27 01:26:21 +0000
commit89e3b1e0b2b59b7924b4c7d696f082288dd5b99e (patch)
tree4dc2c9bdb6940ca14399d2b658c1081da62da29b /controle-20081202.tex
parent161fb17a167ab7ca2e081978c907eae7cd5ec0d0 (diff)
downloadinfmdi720-89e3b1e0b2b59b7924b4c7d696f082288dd5b99e.tar.gz
infmdi720-89e3b1e0b2b59b7924b4c7d696f082288dd5b99e.tar.bz2
infmdi720-89e3b1e0b2b59b7924b4c7d696f082288dd5b99e.zip
More exercices (notably the p-1 method).
Diffstat (limited to 'controle-20081202.tex')
-rw-r--r--controle-20081202.tex155
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 ?
%
%