diff options
| -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�? % % |