%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} \usepackage[latin1]{inputenc} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \usepackage{url} % \theoremstyle{definition} \newtheorem{comcnt}{Tout} \newcommand\exercice{% \refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} \newcommand{\limp}{\mathrel{\Rightarrow}} \newcommand{\liff}{\mathrel{\Longleftrightarrow}} \newcommand{\pgcd}{\operatorname{pgcd}} \newcommand{\ppcm}{\operatorname{ppcm}} \newcommand{\signe}{\operatorname{signe}} \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Fr}} % \newif\ifcorrige \corrigetrue \newenvironment{corrige}% {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% \smallbreak\noindent{\textit{Corrigé.}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\relax\else\egroup\fi\par} % % % \begin{document} \ifcorrige \title{INFMDI720\\Contrôle de connaissance --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}} \else \title{INFMDI720\\Contrôle de connaissance\\{\normalsize Rappels mathématiques pour la cryptographie}} \fi \author{} \date{2 décembre 2008} \maketitle \pretolerance=10000 \tolerance=8000 \vskip1truein\relax \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 vivement recommandé de les traiter dans cet ordre. Le sujet étant volontairement trop long pour le temps imparti, il ne sera pas nécessaire de traiter tous les exercices pour avoir le maximum des points. Il est suggéré de prendre le temps de tous les lire, pour bien choisir ceux que l'on traitera. Il n'est pas nécessaire de faire des réponses longues. L'usage de tous les documents (notes de cours manuscrites ou imprimées, livres) est autorisée. L'usage des calculatrices électroniques est interdites. (Certains exercices peuvent apparaître calculatoires, mais les calculs sont toujours faisables à la main en un temps raisonnable, parfois au prix de quelques astuces.) Durée : 1h30 \newpage % % % \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$) ? \begin{corrige} (1) Comme $11$ et $31$ sont premiers entre eux, le théorème chinois affirme $\mathbb{Z}/341\mathbb{Z} \cong (\mathbb{Z}/11\mathbb{Z}) \times (\mathbb{Z}/31\mathbb{Z})$, donc il suffit de prouver $a^{31} \equiv a \pmod{31}$ et $a^{31} \equiv a \pmod{11}$ pour tout $a \in\mathbb{Z}$. Or on a $a^{31} \equiv a \pmod{31}$ d'après le petit théorème de Fermat ; s'agissant de la relation modulo $11$, on a $a^{10} \equiv 1 \pmod{11}$ si $11$ ne divise pas $a$ (théorème d'Euler), donc $a^{30} = (a^{10})^3 \equiv 1 \pmod{11}$ donc $a^{31} \equiv a \pmod{11}$, et ceci est aussi vrai lorsque $a \equiv 0 \pmod{11}$, donc dans tous les cas $a^{31} \equiv a \pmod{11}$. (2) Le théorème d'Euler ne suffit pas, car $\varphi(128) = 64$ donc il donne seulement $a^{64} \equiv 1 \pmod{128}$ lorsque $a$ est impair (ce qui équivaut à premier à $128$). En revanche, on sait (cours) que $(\mathbb{Z}/128\mathbb{Z})^\times = (\mathbb{Z}/2^7\mathbb{Z})^\times$ n'a pas d'éléments primitifs : il est produit d'un groupe cyclique d'ordre $2$ (engendré par $-1$) et d'un groupe cyclique d'ordre $2^5 = 32$ (engendré par $5$). Si on note ces deux groupes multiplicativement, on a $a^{32} = a$ dans chacun d'entre eux par le théorème de Lagrange, donc c'est le cas dans $(\mathbb{Z}/128\mathbb{Z})^\times$. \end{corrige} % % % \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 », « Imix », « Ik », « Akbal », « Kan », « Chicchan », « Cimi », « Manik », « Lamat », « Muluc », « Oc », « Chuen », « Eb », « Ben », « Ix », « Men », « Cib », « Caban », « Etznab » et « Caunac »). Ces deux cycles sont complètement indépendants, c'est-à-dire que si un jour est numéroté « 11 Ahau », le lendemain sera « 12 Imix », puis « 13 Ik », puis « 1 Akbal », « 2 Kan » et ainsi de suite jusqu'à « 4 Caunac » auquel suit « 5 Ahau », etc. Il n'existe aucune irrégularité. (1) Quelle est le nombre de jours d'un cycle du Tzolkin ? Autrement dit, au bout de combien de jours après un jour donné retombe-t-on pour la première fois sur un jour ayant le même numéro et le même nom ? (2) Sachant que le 2 décembre 2008 est dénommé « 6 Ahau », déterminer quand aura lieu le prochain jour « 10 Oc » au calendrier religieux maya. (3) Les Mayas utilisaient également un calendrier civil (ou Haab) de $365$ jours exactement\footnote{Ce calendrier était lui-même organisé en mois, mais cela ne nous importe pas ici.}, qui se répétait lui aussi sans irrégularité, et complètement indépendamment du calendrier religieux Tzolkin. Quelle est la longueur approximative en années d'un cycle complet des deux calendriers ? Autrement dit, combien d'années faut-il attendre approximativement, à partir d'un jour donné, pour retrouver pour la première fois un jour ayant la même dénomination dans les deux calendriers (Tzolkin et Haab) à la fois ? \begin{corrige} (1) Le cycle complet du Tzolkin est le plus petit nombre multiple à la fois de $13$ (à cause du cycle de $13$ jours) et de $20$ (à cause du cycle de $20$ jours), c'est-à-dire le ppcm de $13$ et de $20$. Comme $13$ et $20$ sont premiers entre eux, c'est $13\times 20 = 260$. (2) Si le prochain jour « 10 Oc » a lieu $n$ jours après le 2 décembre 2008 (6 Ahau), alors $n \equiv 4 \pmod{13}$ puisque dans le cycle de $13$ jours on est passé de $6$ à $10$, et $n \equiv 10 \pmod{20}$ puisqu'on est $10$ dieux plus loin dans le cycle de $20$ jours. On a la relation de Bézout $2\times 20 - 3\times 13 = 1$, donc $n$ est congru à $(4 \times 2) \times 20 - (10 \times 3) \times 13$ modulo $260$ : dans cette expression, il suffit de calculer $10\times 3$ modulo $20$ (c'est $10$), on trouve donc $8\times 20 - 10\times 13 = 160-130 = 30$ (on vérifie $30 \equiv 4 \pmod{13}$ et $30 \equiv 10 \pmod{20}$) : le prochain « 10 Oc » a donc lieu $30$ jours après le 2 décembre 2008 (c'est-à-dire le 1er janvier 2009). (3) Le cycle complet du calendrier (Tzolkin+Haab) est le plus petit nombre multiple à la fois de $260$ (à cause du Tzolkin) et de $365$ (à cause du Haab), c'est-à-dire le ppcm de $260 = 2^2\times 5 \times 13$ et de $365 = 5 \times 73$ : c'est donc $2^2\times 5 \times 13 \times 73$, c'est-à-dire $2^2\times 13\times 365$ jours, ou encore environ $2^2\times 13 = 52$ ans. \end{corrige} % % % \exercice Soit $n = 2^{100}$ et $N = 2^n = 2^{2^{100}}$. (1) Quel est le reste de la division euclidienne de $n$ par $3$ et par $5$ ? % Réponses : 1, 1 (2) Quel est le reste de la division euclidienne de $n$ par $6$, par $10$ et par $4$ ? % Réponses : 4, 6, 0 (3) Quel est le reste de la division euclidienne de $N$ par $9$, par $11$ et par $10$ ? % Réponses : 7, 9, 6 (4) Quel est le reste de la division euclidienne de $N$ par $99$ ? Par $990$ ? % Réponses : 97, 196 \begin{corrige} (1) Le théorème d'Euler (ou une vérification naïve immédiate) assure que $2^2 \equiv 1 \pmod{3}$. Par conséquent, $2^{100} = (2^2)^{50} \equiv 1^{50} = 1 \pmod{3}$. De même, modulo $5$, on a (toujours par Euler ou vérification naïve) $2^4 \equiv 1 \pmod {5}$ donc $2^{100} = (2^5)^{25} \equiv 1^{25} = 1 \pmod{5}$. (2) Le théorème chinois assure que la classe de congruence de $n$ modulo $6$ dépend de celles de $n$ modulo $2$ et $3$. La question précédente a déterminé la classe de $n$ modulo $3$ (c'est $1$), et on a visiblement $n = 2^{100} \equiv 0 \pmod{2}$ (manifestement, $2^{100}$ est pair...). Pour reconstituer $n$ modulo $6$, on cherche donc un nombre congru à $1$ modulo $3$ et à $0$ modulo $2$ : on peut chercher une relation de Bézout ($3-2=1$), mais il est plus simple d'examiner rapidement les différentes classes possibles entre $0$ et $5$ : visiblement $4$ convient, donc $n \equiv 4 \pmod{6}$. De même, pour déterminer la classe de $n$ modulo $10$, le théorème chinois assure qu'elle ne dépend que de $n$ modulo $2$ et $5$. Or on a vu $n \equiv 0 \pmod{2}$ et $n \equiv 1 \pmod{5}$. On voit rapidement que $6$ est congru aux mêmes quantités, donc $n \equiv 6 \pmod{10}$. Enfin, il est clair que $2^{100}$ est multiple de $4$ (i.e., congru à $0$ modulo $4$). (3) Le théorème d'Euler assure que $2^6 \equiv 1 \pmod{9}$ (on a $\varphi(9) = \frac{2}{3}\times 9 = 6$). Par conséquent, $2^{6k} = (2^6)^k \equiv 1^{k} = 1 \pmod{9}$ pour tout $k \in \mathbb{N}$. Or on a vu à la question précédente que $n = 2^{100}$ peut s'écrire sous la forme $6k + 4$ : on a donc $2^n = 2^{6k+4} \equiv 2^4 \equiv 7 \pmod{9}$. Modulo $11$, le raisonnement est analogue : le théorème d'Euler (ou Fermat) assure que $2^{10} \equiv 1 \pmod{11}$. Par conséquent, $2^{10k} = (2^{10})^k \equiv 1^k = 1 \pmod{11}$ pour tout $k \in \mathbb{N}$. Or on a vu que $n = 2^{100}$ peut s'écrire sous la forme $10k+6$ : on a donc $2^n = 2^{10k+6} \equiv 2^6 \equiv 9 \pmod{11}$. Modulo $10$, on ne peut pas appliquer le même raisonnement ($2$ n'est pas premier à $10$ !), mais on peut appliquer celui des questions (1) et (2) : on a vu $n \equiv 0 \pmod{4}$, c'est-à-dire qu'on peut écrire $n = 4k$ (avec $k = 2^{98}$ mais peu importe), donc $2^n = (2^4)^k \equiv 1^k = 1 \pmod{5}$, et comme $2^n \equiv 0 \pmod{2}$, on a $2^n \equiv 6 \pmod{10}$ (exactement comme on l'a fait en (2)). (4) Il s'agit enfin d'appliquer le théorème chinois de façon effective pour reconstituer la classe de $N$ modulo $99$ puis $990$ à partir de ses classes modulo $9$, $11$ et $10$, déjà calculées (soit $N \equiv 7 \pmod{9}$, $N \equiv 9 \pmod{11}$ et $N \equiv 6 \pmod{10}$). Trouvons une relation de Bézout entre $9$ et $11$ (qui sont bien premiers entre eux !). Pour cela, on peut appliquer l'algorithme d'Euclide étendu, qui termine en deux divisions : $11 = 1\times 9 + 2$ puis $9 = 4\times 2 + 1$, donc $1 = 1\times 9 - 4\times 2$ et ($2 = 11 - 1\times 9$ donc) $1 = 5\times 9 - 4\times 11$ (on pouvait aussi trouver rapidement cette relation en cherchant dans les petits multiples de $9$ et $11$ lesquels deux sont consécutifs). On sait donc (cours) que $N \equiv 9\times 5\times 9 - 7\times 4\times 11 \pmod{99}$ : pour faire ce calcul plus simplement à la main, on peut réduire $9\times 5$ modulo $11$ et $7\times 4$ modulo $9$, ce qui fait respectivement $1$ et $1$, donc $N \equiv 1\times 9 - 1\times 11 = -2 \equiv 97 \pmod{99}$. Enfin, reconstruisons $N$ modulo $990$ à partir de $N \equiv 6 \pmod{10}$ et $N \equiv 97 \pmod{99}$. Une relation de Bézout entre $99$ et $10$ est évidente : c'est $10\times 10 - 1\times 99 = 1$. Par conséquent, $N \equiv 97\times 10\times 10 - 6\times 1\times 99 \pmod{990}$. De nouveau, pour simplifier les calculs, on peut se contenter de calculer $97\times 10 \equiv (-2)\times 10 = -20$ modulo $99$ et $-6\times 1 \equiv 4 \pmod{10}$, donc on a $N \equiv -20\times 0 + 4\times 99 = 196 \pmod{990}$. \end{corrige} % % % \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$. (1a) Si $n$ est impair, montrer que $\varphi(2n) = \varphi(n)$. (1b) Si $n$ est pair mais non multiple de $4$, montrer que $\varphi(\frac{1}{2}n) = \varphi(n)$. (1c) Si $n$ est multiple de $4$ mais non de $12$, montrer que $\varphi(\frac{3}{2}n) = \varphi(n)$. (1d) Si $n$ est multiple de $12$ mais non de $36$, montrer que $\varphi(\frac{2}{3}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 ? \begin{corrige} Rappelons du cours que si $u$ et $v$ sont premiers entre eux, on a \[ \varphi(uv) = \varphi(u)\,\varphi(v)\tag{*} \] (c'est une conséquence immédiate du théorème chinois $(\mathbb{Z}/uv\mathbb{Z})^\times \cong (\mathbb{Z}/u\mathbb{Z})^\times \times (\mathbb{Z}/v\mathbb{Z})^\times$ en prenant les cardinaux). \textit{A contrario}, si $u$ est divisible par chaque nombre premier divisant $v$ (par exemple si $u|v$), on a \[ \varphi(uv) = u \, \varphi(v)\tag{\textdagger} \] puisque $\varphi(v) = v\prod_{p|v}(1-\frac{1}{p})$ et $\varphi(uv) = uv\prod_{p|uv}(1-\frac{1}{p})$, le produit portant sur le même ensemble de nombres premiers $p$. (1a) Si $n$ est impair, c'est-à-dire si $2$ et $n$ sont premiers entre eux, alors $\varphi(2n) = \varphi(2)\,\varphi(n) = \varphi(n)$ d'après (*) (remarquer $\varphi(2)=1$). (1b) Si $n$ est pair mais non multiple de $4$, le nombre $\frac{1}{2}n$ est un entier impair, donc de nouveau $\varphi(n) = \varphi(2\,\frac{1}{2}n) = \varphi(2)\,\varphi(\frac{1}{2}n) = \varphi(\frac{1}{2}n)$ d'après (*). (1c) Si $n$ est multiple de $4$ mais non de $12$, le nombre $\frac{1}{2}n$ est un entier pair mais non multiple de $3$ (donc premier à lui), donc d'une part $\varphi(\frac{3}{2}n) = \varphi(3\,\frac{1}{2}n) = \varphi(3)\,\varphi(\frac{1}{2}n) = 2\varphi(\frac{1}{2}n)$ d'après (*) (remarquer $\varphi(3)=2$) et d'autre part $\varphi(n) = \varphi(2\,\frac{1}{2}n) = 2\varphi(\frac{1}{2}n)$ d'après (\textdagger). En rassemblant ces deux égalités, on a $\varphi(\frac{3}{2}n) = \varphi(n)$. (1d) Si $n$ est multiple de $12$ mais non de $36$, le nombre $\frac{1}{3}n$ est un entier pair mais non multiple de $3$, donc d'une part $\varphi(n) = \varphi(3\,\frac{1}{3}n) = \varphi(3)\,\varphi(\frac{1}{3}n) = 2\varphi(\frac{1}{3}n)$ d'après (*) et d'autre part $\varphi(\frac{2}{3}n) = \varphi(2\,\frac{1}{3}n) = 2\varphi(\frac{1}{3}n)$ d'après (\textdagger). En rassemblant ces deux égalités, on a $\varphi(\frac{2}{3}n) = \varphi(n)$. (1e) Si $n$ est multiple de $36$ mais non de $252$, le nombre $\frac{1}{6}n$ est un entier multiple de $6$ mais non multiple de $7$, donc d'une part $\varphi(\frac{7}{6}n) = \varphi(7\,\frac{1}{6}n) = \varphi(7)\,\varphi(\frac{1}{6}n) = 6\varphi(\frac{1}{6}n)$ d'après (*) (remarquer $\varphi(7)=6$) et d'autre part $\varphi(n) = \varphi(6\,\frac{1}{6}n) = 6\varphi(\frac{1}{6}n)$ d'après (\textdagger). En rassemblant ces deux égalités, on a $\varphi(\frac{7}{6}n) = \varphi(n)$. (1f) Si $n$ est multiple de $252$ mais non de $1764$, le nombre $\frac{1}{7}n$ est un entier multiple de $6$ mais non multiple de $7$, donc d'une part $\varphi(n) = \varphi(7\,\frac{1}{7}n) = \varphi(7)\,\varphi(\frac{1}{7}n) = 6\varphi(\frac{1}{7}n)$ d'après (*) et d'autre part $\varphi(\frac{6}{7}n) = \varphi(6\,\frac{1}{7}n) = 6\varphi(\frac{1}{7}n)$ d'après (\textdagger). En rassemblant ces deux égalités, on a $\varphi(\frac{6}{7}n) = \varphi(n)$. (2) De façon exactement analogue à (1c) et (1e), si $n$ est multiple de $6^2\times 7^2 = 1764$ mais non de $6^2\times 7^2\times 43$, on montre que $\varphi(\frac{43}{42}n) = \varphi(n)$. De façon exactement analogue à (1d) et (1f), si $n$ est multiple de $6^2\times 7^2\times 43$ mais non de $6^2\times 7^2\times 43^2$, on montre que $\varphi(\frac{42}{43}n) = \varphi(n)$. Appelons $n$ un entier qui ne vérifie pas la conjecture, s'il existe. D'après (1a), $n$ doit être pair (car les entiers impairs vérifient la conjecture). D'après (1b), il doit donc être multiple de $4$. D'après (1c), il doit alors être multiple de $12$. D'après (1d), il doit alors être multiple de $36$. D'après (1e), il doit alors être multiple de $36\times 7 = 252$. D'après (1f), il doit alors être multiple de $36\times 7^2 = 1764$. D'après le paragraphe précédent, il doit alors être multiple de $6^2\times 7^2\times 43$, puis de $6^2\times 7^2\times 43^2$. (On ne peut plus ensuite continuer ce petit jeu de façon aussi mécanique, puisque $6\times 7\times 43 + 1 = 1807$ n'est plus premier.) (3) Si $n$ est multiple de $(6\times 7 \times 43)^2$ mais ni de $27$ ni de $13$, le nombre $\frac{1}{18}n$ est un entier multiple de $2$ mais non multiple de $3$ ni de $7$, donc d'une part $\varphi(\frac{13}{18}n) = \varphi(13\,\frac{1}{18}n) = \varphi(13)\,\varphi(\frac{1}{18}n) = 12\varphi(\frac{1}{18}n)$ d'après (*) et d'autre part $\varphi(n) = \varphi(9\times 2 \times \frac{1}{18}n) \buildrel\textrm{(*)}\over= \varphi(9)\varphi(2\,\frac{1}{18}n) = 6 \varphi(2\,\frac{1}{18}n) \buildrel\textrm{(\textdagger)}\over= 6\times 2\times \varphi(\frac{1}{18}n) = 12\varphi(\frac{1}{18}n)$. En rassemblant ces deux égalités, on a $\varphi(\frac{13}{18}n) = \varphi(n)$. (4) Si $n$ ne vérifie pas la conjecture, on sait déjà qu'il doit être multiple de $6^2\times 7^2\times 43^2$, et la question (3) montre qu'il doit de plus l'être de $27$ (donc de $2^2\times 3^3\times 7^2\times 43^2$) ou bien de $13$ (donc de $2^2\times 3^2\times 7^2\times 13\times 43^2$). Il doit donc au moins être égal à $2^2\times 3^3\times 7^2\times 43^2 \geq 9\times 10^6$. On a donc montré que la conjecture était vraie au moins pour les neuf millions de premiers entiers naturels. \end{corrige} % % % \exercice 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