diff options
Diffstat (limited to 'controle-20081202.tex')
| -rw-r--r-- | controle-20081202.tex | 155 |
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 ? % % |