\documentclass[a4paper,12pt]{article} \usepackage[french]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{amssymb,amsthm,amsmath,amsfonts,mathrsfs} \usepackage{hyperref} \newtheoremstyle{custom}% {\topsep}% {\topsep}% {\normalfont}% {}% {\bfseries}% {.}% {\newline}% (default .5em) {}% \theoremstyle{custom} \usepackage{textcomp} %\usepackage{bbm} \usepackage{geometry} \usepackage{mathrsfs} \usepackage{enumitem} \usepackage{csquotes} %\usepackage{esvect} % Pour des vecteurs \usepackage{hyperref} %Pour des liens hypertexte ! \hypersetup{ % backref=true, %permet d'ajouter des liens dans... % pagebackref=true,%...les bibliographies % hyperindex=true, %ajoute des liens dans les index. colorlinks=true, %colorise les liens % breaklinks=true, %permet le retour à la ligne dans les liens trop longs % urlcolor= blue, %couleur des hyperliens % linkcolor= black, %couleur des liens internes % linktoc =all, %defines which part of an entry in the table of contents is made into a link % citecolor=black, %color of citation links (bibliography) % filecolor=black, %color of file links % bookmarks=true, %créé des signets pour Acrobat bookmarksopen=true, %si les signets Acrobat sont créés, %les afficher complètement. pdftitle={M1 algèbre effective}, %informations apparaissant dans pdfauthor={Samuel Le Fourn}, %dans les informations du document } \frenchspacing \newtheorem{thm}{Théorème}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{cor}[thm]{Corollaire} \newtheorem*{thmsansnom}{Théorème} \newtheorem*{propsansnom}{Proposition} \newtheorem{lem}[thm]{Lemme} \theoremstyle{custom} \newtheorem{defi}[thm]{Définition} \newtheorem{rem}[thm]{Remarque} \newtheorem{exe}[thm]{Exemple} \newtheorem{exocours}[thm]{Exercice de cours} \newtheorem{exerciseaux}[thm]{Exercice} %\newenvironment{exo}{\begin{exerciseaux}\leavevmode\par}{\end{exo}} \newtheorem{exo}[thm]{Exercice} \def\R{\mathbb{R}} \def\C{\mathbb{C}} \def\N{\mathbb{N}} \def\Z{\mathbb{Z}} \def\Q{\mathbb{Q}} \def\F{\mathbb{F}} \def\1{\mathbbm{1}} \def\Ncal{\mathcal{N}} \DeclareMathOperator{\pgcd}{pgcd} \DeclareMathOperator{\ppcm}{ppcm} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\Inn}{Inn} \DeclareMathOperator{\id}{id} \newcommand{\Ker}{\operatorname{Ker}} \setlist{noitemsep} \setlist[1]{labelindent=\parindent} % < Usually \setlist[itemize]{leftmargin=*} %d\setlist[itemize]{label = ($(\arabic*)$)} \setlist[enumerate]{label = ($\alph*$)} %%%%%%%%%%%%%%%%%% % Alphabet Grec % %%%%%%%%%%%%%%%%%% \renewcommand{\a}{\alpha} \renewcommand{\b}{\beta} \newcommand{\g}{\gamma} \renewcommand{\d}{\delta} \newcommand{\e}{\epsilon} \newcommand{\f}{\varphi} \renewcommand{\l}{\lambda} \renewcommand{\k}{\kappa} \newcommand{\m}{\mu} \newcommand{\n}{\nu} \renewcommand{\o}{\omega} \renewcommand{\r}{\rho} \newcommand{\s}{\sigma} \renewcommand{\t}{\tau} \newcommand{\z}{\zeta} \newcommand{\D}{\Delta} \newcommand{\G}{\Gamma} %%%%%%%%%%%%%%%%%%%% % Alphabet gothique% %%%%%%%%%%%%%%%%%%%% \newcommand{\ga}{{\mathfrak{a}}} \newcommand{\gA}{{\mathfrak{A}}} \newcommand{\gb}{{\mathfrak{b}}} \newcommand{\gB}{{\mathfrak{B}}} \newcommand{\gc}{{\mathfrak{c}}} \newcommand{\gC}{{\mathfrak{C}}} \newcommand{\gd}{{\mathfrak{d}}} \newcommand{\gD}{{\mathfrak{D}}} \newcommand{\gI}{{\mathfrak{I}}} \newcommand{\gm}{{\mathfrak{m}}} \newcommand{\gn}{{\mathfrak{n}}} \newcommand{\go}{{\mathfrak{o}}} \newcommand{\gO}{{\mathfrak{O}}} \newcommand{\gp}{{\mathfrak{p}}} \newcommand{\qg}{{\mathfrak{q}}} \newcommand{\gP}{{\mathfrak{P}}} \newcommand{\gQ}{{\mathfrak{Q}}} \newcommand{\gq}{{\mathfrak{q}}} \newcommand{\gR}{{\mathfrak{R}}} \newcommand{\gS}{{\mathfrak{S}}} \newcommand{\gJ}{{\mathfrak{J}}} %%%%%%%%%%%%%%%%%%%%%%%%%%% % Alphabet calligraphique % %%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\Acal}{{\mathcal A}} \newcommand{\Bcal}{{\mathcal B}} \newcommand{\Ccal}{{\mathcal C}} \newcommand{\Dcal}{{\mathcal D}} \newcommand{\Ecal}{{\mathcal E}} \newcommand{\Fcal}{{\mathcal F}} \newcommand{\Gcal}{{\mathcal G}} \newcommand{\Hcal}{{\mathcal H}} \newcommand{\Ical}{{\mathcal I}} \newcommand{\Jcal}{{\mathcal J}} \newcommand{\Kcal}{{\mathcal K}} \newcommand{\Lcal}{{\mathcal L}} \newcommand{\Mcal}{{\mathcal M}} \newcommand{\Ocal}{{\mathcal O}} \newcommand{\Pcal}{{\mathcal P}} \newcommand{\Qcal}{{\mathcal Q}} \newcommand{\Rcal}{{\mathcal R}} \newcommand{\Scal}{{\mathcal S}} \newcommand{\Tcal}{{\mathcal T}} \newcommand{\Ucal}{{\mathcal U}} \newcommand{\Vcal}{{\mathcal V}} \newcommand{\Wcal}{{\mathcal W}} \newcommand{\Xcal}{{\mathcal X}} \newcommand{\Ycal}{{\mathcal Y}} \newcommand{\Zcal}{{\mathcal Z}} %%%%%%%%%%%%%%%%%%%% % Alphabet en gras % %%%%%%%%%%%%%%%%%%%% \newcommand{\ab}{\mathbf{a}} %%%%%%%%%%%%%%%%%%%% % Ensembles usuels % %%%%%%%%%%%%%%%%%%%% \renewcommand{\P}{\mathbb{P}} \newcommand{\Fp}{{\mathbb{F}_{\! p}}} \newcommand{\A}{{\mathbb{A}}} \newcommand{\T}{{\mathbb{T}}} %%%%%%%%%%%%%%%%%%%%% % Opérateurs usuels % %%%%%%%%%%%%%%%%%%%%% \newcommand{\Card}{\operatorname{Card}} \newcommand{\Crit}{\operatorname{Crit}} \renewcommand{\div}{\operatorname{div}} \newcommand{\Div}{\operatorname{Div}} \newcommand{\End}{\operatorname{End}} \newcommand{\Gal}{\operatorname{Gal}} \newcommand{\SL}{\operatorname{SL}} \newcommand{\Id}{\operatorname{Id}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\mult}{\operatorname{mult}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\Proj}{\operatorname{Proj}} \newcommand{\Spec}{\operatorname{Spec}} \newcommand{\Borel}{\operatorname{Borel}} \newcommand{\Stab}{\operatorname{Stab}} \newcommand{\Cart}{\operatorname{Cart}} \newcommand{\Cot}{\operatorname{Cot}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cl}{\operatorname{cl}} \newcommand{\gr}{\operatorname{gr}} \newcommand{\init}{\operatorname{in}} \newcommand{\PGL}{\operatorname{PGL}} \newcommand{\PSL}{\operatorname{PSL}} \newcommand{\Der}{\operatorname{Der}} \newcommand{\num}{\operatorname{num}} \renewcommand{\Re}{\operatorname{Re}} \newcommand{\im}{\operatorname{im}} \newcommand{\Jac}{\operatorname{Jac}} \newcommand{\Vect}{\operatorname{Vect}} \newcommand{\car}{\operatorname{car}} \newcommand{\Sp}{\operatorname{Sp}} \newcommand{\Pic}{\operatorname{Pic}} \newcommand{\carac}{\textrm{char}} \newcommand{\Tr}{\operatorname{Tr}} \renewcommand{\mod}{\, \operatorname{mod} \,} \newcommand{\Frac}{\operatorname{Frac}} \newcommand{\preuve}{\textcolor{blue}{$^{(P)}$}} %%%%%%%%%%% % Flèches % %%%%%%%%%%% \newcommand{\mt}{\mapsto} \newcommand{\lmt}{\longmapsto} \newcommand{\ra}{\rightarrow} \newcommand{\lra}{\longrightarrow} \newcommand{\La}{\Leftarrow} \newcommand{\Ra}{\Rightarrow} \newcommand{\Lra}{\Leftrightarrow} \newcommand{\Llra}{\Longleftrightarrow} \newcommand{\dessin}{\textcolor{green}{(D)}} %%% Commandes spécifiques à la géométrie affine %%%% %\newcommand{Evect}{\overrightarrow{E}} %\newcommand{Fvect}{\overrightarrow{F}} %\newcommand{uvect}{\overrightarrow{u}} %\newcommand{vvect}{\overrightarrow{v}} %%%%%%%%%%%%%%%%%% % Macros utiles %% %%%%%%%%%%%%%%%%%% \newcommand{\fonction}[5]{\begin{array}{c|ccl} % Pour écrire une fonction en environnement display : le nom puis espaces de départ et d'arrrivée, puis argument et résultat #1: & #2 & \longrightarrow & #3 \\ & #4 & \longmapsto & #5 \end{array}} \newcommand{\fonctionsansnom}[4]{\begin{array}{ccl} % La même sans le nom de la fonction à mettre #1 & \lra & #2 \\\ #3 & \lmt & #4 \end{array}} \newtheorem{enonce}[thm]{Exercice}%[section] \newenvironment{Ex}[0]{\begin{enonce}\rm}{\bigskip \end{enonce}} %\newtheorem{theoreme}{Th\'eor\`eme}%[section] \geometry{top=2cm, bottom=2cm} \begin{document} \newgeometry{top=1cm,bottom=2cm,left=2cm,right=2cm} \noindent {\large \textsc{Université Grenoble Alpes \hfill M1 \\ \hfill M1 Algèbre effective \hfill 2025-2026}} \\ \hrule \bigskip \begin{center} \textbf{\Large Arithmétique modulaire, primalité} \end{center} \bigskip \section{Exercices} \begin{exo}[Polynômes sans facteurs carrés] \label{ex:polysfc} \begin{enumerate} \item[] \item Rappeler pourquoi pour tout corps fini $K$ et tout $P \in K[X]$, $P$ est sans facteurs carrés (dans sa décomposition en facteurs irréductibles dans $K[X]$) si et seulement si $\operatorname{pgcd}(P,P')=1$. \item Soit $P = X^4 + 13 X + 1 \in \Z/p\Z[X]$. Est-il sans facteurs carrés pour $p=7$ ? $p=11$ ? \end{enumerate} \end{exo} \begin{exo}[Inverses dans des anneaux quotients de polynômes] Soit $P=X^3+X+1 \in \Q[X]$. D\'eterminer l'inverse de $X^2+X+1$ dans $\Q[X]/(P)$. \end{exo} \begin{exo}[\'Ecriture en base $b$] \label{ex:ecriturebaseb} Décrire algorithmiquement comment écrire en base $b$ un entier $n$ initialement écrit en base 10. Quel est le coût de cette écriture ? \end{exo} \begin{exo}[PGCD binaire] \begin{enumerate} \item[] \item Effectuer à la main l'algorithme du PGCD binaire pour 123 et 57 (on partira directement de leurs écritures en base 2). \item Montrer que l'algorithme du PGCD binaire appliqu\'e à 2 entiers de tailles respectives au plus $m$ et $n$ bits n\'ecessite au plus $O(mn)$ opérations élémentaires du microprocesseur. \end{enumerate} \end{exo} \begin{exo}[Algorithme d'Euclide étendu] \label{ex:euclideetendu} \begin{enumerate} \item[] \item Rappeler comment une relation de Bézout entre deux entiers $a$ et $b$ premiers entre eux permet de calculer l'inverse de $a$ modulo $b$ (et inversement). \item Effectuer à la main l'algorithme d'Euclide \'etendu pour 123 et 57. \item En d\'eduire que le pgcd de 123 et 57 est 3, puis calculer l'inverse de 19 modulo 41. \end{enumerate} \end{exo} \begin{exo}[Calcul plus rapide de l'inverse modulaire] \begin{enumerate} \item[] \item Montrer que pour $a,n \in \Z$ premiers entre eux, on peut gagner environ un tiers des calculs pour celui de l'inverse de $a$ modulo $n$ par rapport au calcul des coefficients de B\'ezout pour $a$ et $n$. \item Illustrer sur l'exemple de l'exercice précédent. \end{enumerate} \end{exo} \begin{exo}[Théorème des restes chinois] \label{ex:resteschinois} \begin{enumerate} \item[] \item[] Soient $a$ et $b$ deux entiers premiers entre eux. \item Donner grâce à une relation de Bézout deux entiers $e_a$ et $e_b$ tels $e_a \equiv 1 \mod a, e_a \equiv 0 \mod b$ et $e_b \equiv 0 \mod a$ et $e_b \equiv 1 \mod b$. \item Pour $x,y \in \Z$ quelconques, en déduire un entier $n$ tel que $n \equiv x \mod a$ et $n \equiv y \mod b$. Quel est le coût du calcul complet ? \item Supposons de plus que $a$ est de taille $O(k)$ et $b$ de taille $O(1)$, montrer qu'alors le coût est en $O(k)$. \item Illustrer avec $a=143$, $b=5$, $x=100$ et $y=1$. \end{enumerate} \end{exo} \begin{exo}[Déterminant d'une matrice entière par restes chinois] Soit $M \in M_n(\Z)$ dont les coefficients sont en valeur absolue plus petits qu'une certaine borne $A$. \begin{enumerate}[label=($\alph*$)] \item Montrer que $|\det(M)| \leq (\sqrt{n}A)^n$ (utiliser la borne de Hadamard). \item Soit $M \in M_3(\Z)$ à coefficients plus petits que 10 en valeur absolue. On a calcul\'e le d\'eterminant de $M$ modulo 19, 23 et 29 et trouv\'e 1, 2 et 3. Que vaut le d\'eterminant de $M$~? \item Combien de nombres premiers de taille proche de $A$ faut-il utiliser pour reconstruire le d\'eterminant de $M$ en utilisant les restes chinois et la valeur du d\'eterminant de $M$ modulo ces nombres premiers~? \item Estimer le coût de l'algorithme si le coût de calcul du déterminant modulo un nombre premier est en $O(n^3)$. \end{enumerate} \end{exo} \begin{exo}[Exponentiation rapide d'entiers modulaires] \label{ex:exporapide} \begin{enumerate} \item[] \item Utiliser à la main l'algorithme de la puissance rapide (aussi appel\'e exponentiation rapide) pour calculer $\overline{3}^{1030}$ dans $\Z/19\Z$. \item Vérifier la validité de ce calcul en utilisant que 19 est premier. \end{enumerate} \end{exo} \begin{exo}[Exponentiation naïve vs. exponentiation rapide d'entiers] Soit $a$ un entier. Comparer le cout du calcul de $a^n$ en utilisant la m\'ethode de multiplication naive ($a\times a \times ... \times a$) et le m\^eme algorithme que l'exponentiation modulaire, mais sans modulo. \end{exo} \begin{exo}[Résolution d'équations quadratiques dans les $\Z/n\Z$] \label{ex:racinecarree} \begin{enumerate} \item[] \item R\'esoudre dans $\Z/103\Z$ les \'equations du second degr\'e~: $$ x^2 +3x+5=0, \quad x^2 +3x+6=0.$$ \item Pour $p>2$ premier, montrer que pour tout $a \in (\Z/p\Z)^*$, $a$ est un carré si et seulement si $a^{(p-1)/2} = 1 \mod p$. Si de plus $p = 3 \mod 4$, montrer qu'alors une racine carrée de $a$ modulo $p$ est donnée par $a^{(p+1)/4} \mod p$. \item Estimer le coût pour résoudre une équation de degré 2 dans un corps $\Z/p\Z$ où $p = 3 \mod 4$ est un nombre premier de taille $O(n)$. \end{enumerate} \end{exo} \begin{exo}[Générateurs des $(\Z/p\Z)^*$] \label{ex:generateursZpZ} Estimer le coût moyen pour trouver un générateur de $(\Z/p\Z)^*$ avec $p$ un nombre premier de taille $O(n)$. \end{exo} \begin{exo}[Irréductibilité de polynômes] \begin{enumerate} \item[] \item Le polynôme $P=X^4+X+2 \in \Z/3\Z[X]$ est-il irr\'eductible ? \item Estimer le coût d'un test d'irr\'eductibilit\'e de $P \in (\Z/p\Z)[X]$ unitaire en fonction du degré de $P$ et de la taille de $p$. \item D\'eterminer heuristiquement le coût moyen de construction d'un polyn\^ome unitaire irr\'eductible de degr\'e $n$ dans $(\Z/p\Z)[X]$. \end{enumerate} \end{exo} \section{TP} \subsection{Installation et utilisation de Xcas} \subsubsection{Tablette, smartphone, PC sans installation, calculatrice.} Vous pouvez travailler avec Xcas sans installation avec une version web sur tout matériel disposant d'un navigateur~:\\ \href{https://www-fourier.univ-grenoble-alpes.fr/~parisse/xcas.html}{https://www-fourier.univ-grenoble-alpes.fr/\~\!parisse/xcas.html}\\ \href{https://www-fourier.univ-grenoble-alpes.fr/~parisse/xcasfr.html}{https://www-fourier.univ-grenoble-alpes.fr/\~\!parisse/xcasfr.html}\\ \href{https://xcas.univ-grenoble-alpes.fr/xcasjs/}{https://xcas.univ-grenoble-alpes.fr/xcasjs/} (smartphone)\\ Vous pouvez l'installer sur une calculatrice compatible Casio Graph 90/Math+, HP Prime, Numworks, TI Nspire depuis \href{https://www-fourier.univ-grenoble-alpes.fr/~parisse/}{https://www-fourier.univ-grenoble-alpes.fr/\~\!parisse}\\ La version web permet d'\'echanger tr\`es facilement des sessions par email ou de les publier sur des forums. Ces versions de Xcas sont compatibles entre elles (par exemple: menu Fich/Clone pour passer de Xcas PC \`a Xcas web). \subsubsection{Installation de Xcas sur votre propre ordinateur (recommandé)} %Vous pouvez installer Xcas sur votre ordinateur avec ce lien~:\\ Cf. \href{https://www-fourier.univ-grenoble-alpes.fr/~parisse/install_fr.html}{https://www-fourier.univ-grenoble-alpes.fr/\~\!parisse/install\_fr.html} \subsubsection{Installation et lancement de Xcas sur votre session étudiante (recommandé)} {\bf Configuration}~: à faire lors de la première séance. Ouvrir un terminal, puis taper\\ \verb|emacs ~/.bashrc &|\\ ajouter à la fin du fichier une ligne\\ \verb|export PATH=/home/p/parisseb/bin:$PATH|\\ sauvegarder. Taper ensuite\\ \verb|firefox &|\\ et validez pour faire de Firefox votre navigateur par défaut. Fermer le terminal. {\bf Lancement}~: Ouvrir un terminal et taper \verb!runxcas!\\ Lors de la première utilisation, choisir Xcas en syntaxe compatible Python. Puis menu Cfg, configuration générale, Navigateur, mettre \verb|open| au lieu de \verb|/usr/bin/firefox| et sauvegarder. % \begin{itemize} % \item Télécharger l'archive d'installation : % \verb|wget https://www-fourier.univ-grenoble-alpes.fr/~parisse/giac/giac-1.9.0.tar.gz|\\ % \item Extraire l'archive : % \verb|tar xvfa ~/Téléchargements/giac-1.9.0.tar.gz ; cd giac-1.9.0;| % % \verb|; ./configure --prefix=$HOME| % \item Compiler (\verb|make -j|) et installer (\verb|make install|) % % \item Création de raccourci : créer un fichier \verb|runxcas| contenant\\ % \verb|export LD_LIBRARY_PATH=$HOME/lib ;|\\ % \verb|export XCAS_ROOT=$HOME/share/giac ; ~/bin/xcas &|\\ % qui permet de lancer Xcas en tapant \verb|sh runxcas| % \item Ensuite, en salle TP, pour ouvrir Xcas vous n'aurez plus qu'à ouvrir un terminal et taper % %\verb|xcas &| % % \verb|~parisseb/bin/runxcas| % % (il n'y a pas d'aide avec \verb|xcas &|...). % \end{itemize} \subsection{Principe de fonctionnement de Xcas} % Xcas est un shell, un peu comme en Python : on tape une ligne de commande ou un programme dans un \'editeur de programmes, on valide par Enter ou OK, et Xcas renvoie une valeur ou affiche un graphe ou indique une erreur. \begin{itemize} \item Pour vous familiariser avec les commandes de Xcas et leur syntaxe vous pouvez utiliser les menus de Xcas (Outil, Expression, Graphes, Cmds), les assistants math\'ematiques dans Xcas web, ou les menus sur calculatrices, ainsi que l'index des commandes (menuq Aide, Index dans Xcas). \item La touche de tabulation permet de compl\'eter un d\'ebut de nom de commande ou/et d'afficher l'aide sur cette commande. On peut recopier un exemple de commande de l'aide et modifier les valeurs des arguments. Ou suivez le tutoriel de Xcas (menu Aide, D\'ebuter en calcul formel). \item Pour saisir une matrice (liste de listes de m\^eme taille), on peut utiliser la commande \verb|matrix|, ou entrer les coefficients un par un en ligne de commandes (par exemple \verb|[[1,a],[a,1]]|) ou avec le tableur (Tableur, nouveau tableur, donner un nom de variable et entrer les coefficients). \item Pour \'ecrire un programme, vous pouvez choisir la syntaxe compatible Python de Xcas, la structuration d'un programme est alors identique \`a Python (\verb|def/return, if/else, for/while|) (Xcas propose d'autres syntaxes~: mots-clefs en fran\c{c}ais ou compatibles avec C/Javascript.). La configuration courante du logiciel est affichée dans la barre d'\'etat, en particulier la syntaxe (compatible Python ou en fran\c{c}ais), cliquer pour la modifier. \item Pour mettre au point un programme, vous pouvez utiliser le d\'ebugger qui permet d'ex\'ecuter en pas \`a pas un programme (commande \verb|debug|). \item {\bf Faites des sauvegardes r\'eguli\`erement, faites-en syst\'ematiquement avant de tester un programme} (Xcas a un m\'ecanisme de sauvegarde automatique en cas de crash, mais deux pr\'ecautions valent mieux qu'une). Lorsque vous ouvrez une session sauvegard\'ee, le contenu des variables est restaur\'e, sauf si vous avez ouvert en mode de r\'ecup\'eration. Le menu Edit, Exe\'ecuter session, permet de r\'eex\'ecuter toute la session. \end{itemize} \subsection{Prise en main de Xcas} \begin{enumerate} \item \'Ecrire le polyn\^ome $(x+3)^7 \times (x-5)^6$ selon les puissances d\'ecroissantes de $x$. \item Simplifier les expressions suivantes: \[ \quad \sqrt{3+2\sqrt{2}}, \quad \frac{1+\sqrt{2}}{1+2\sqrt{2}}, \quad e^{i\pi/6}, \quad 4\mbox{arctan}\left(\frac{1}{5}\right)-\mbox{arctan}\left(\frac{1}{239}\right) \] \item Factoriser~: \[ x^8-3x^7-25x^6+99x^5+60x^4-756x^3+1328x^2-960x+256 \] \[ x^6-2x^3+1, \quad (-y+x)z^2-xy^2+x^2y \] (dans quel anneau de polynômes ces factorisations sont-elles calculées par défaut ?) \item Calculer les sommes suivantes \[\sum_{k=1}^N k,\ \sum_{k=1}^N k^2,\ \sum_{k=1}^\infty \frac{1}{k^2}\] \item Trouver les entiers $n$ tels que le reste de la division euclidienne de $123 n $ par 256 soit 17. \item D\'eterminer la liste des diviseurs de 45768. Factoriser 100! \item R\'esoudre le syst\`eme lin\'eaire: \[ \left\{ \begin{array}{lllllll} x &+& y &+& az&=&1\\ x & +& a y&+& z&=&2 \\ ax & +&y &+& z&=&3 \end{array}\right. \] D\'eterminer l'inverse de la matrice du syst\`eme ci-dessus, puis la diagonaliser. %Diagonaliser la matrice $A$. \end{enumerate} \subsection{TP d'arithmétique} \begin{exo}[Vérification des calculs] Vérifier (ou faire) les calculs faits dans les exercices plus haut. \end{exo} \begin{exo}[Programmation des algorithmes évoqués] \'Ecrire les algorithmes mentionnés ou considérés dans les exercices de TD, à savoir : \begin{itemize} \item Le test si un polynôme est sans facteurs carrés de l'exercice \ref{ex:polysfc}. \item L'écriture en base $b$ d'un entier écrit dans une base autre (par exemple 10) de l'exercice \ref{ex:ecriturebaseb}. \item L'algorithme d'Euclide étendu, le calcul d'inverse modulaire et le théorème des restes chinois pour deux entiers premiers entre eux des exercices \ref{ex:euclideetendu} et \ref{ex:resteschinois} (bonus : l'étendre pour $n$ entiers premiers entre eux deux à deux). \item L'exponentiation rapide d'entiers modulaires de l'exercice \ref{ex:exporapide}. \end{itemize} \end{exo} \begin{exo} Tester le temps de calcul du produit de grands entiers. \end{exo} \begin{exo}[Avantages de l'exponentiation rapide] Comparer le temps de calcul de $a^n \mod m$ par la fonction \verb!powmod! et celui donné en calculant $a^n$ puis en prenant son reste modulo $m$. \end{exo} \begin{exo}[Générateur de $(\Z/p\Z)^*$ sous condition] Soit $p$ premier tel qu'on connaît tous les facteurs premiers $d$ de $p-1$. \begin{enumerate} \item Montrer que $a \in \Z$ premier à $p$ engendre $(\Z/p\Z)^*$ si et seulement si $a^{(p-1)/d} \neq 1 \mod p$ pour tout facteur premier $d$ de $p-1$. \item \'Ecrire un algorithme de recherche de générateur de $(\Z/p\Z)^*$ basé sur cette propriété et comparer avec celle du coût moyen de l'exercice \ref{ex:generateursZpZ}. \end{enumerate} \end{exo} \begin{exo}[Test de primalité naïf et crible d'Eratosthène] \begin{enumerate} \item[] \item \'Ecrire un algorithme testant si un nombre $n$ est premier par division. Discuter sa complexité et expérimenter. \item Pour $n \geq 2$, écrire l'algorithme du crible d'Eratosthène renvoyant la liste des nombres premiers entre $2$ et $n$ (cet algorithme ne doit pas utiliser de division, seulement des additions). Estimer sa complexité. \end{enumerate} \end{exo} \newpage \begin{exo}[Racine carrée modulo $p$] Soit $p$ un nombre premier. \begin{enumerate} \item \'Ecrire un programme trouvant (si elle existe) une racine carrée d'un entier $n$ modulo $p$. \item Si $p \equiv 3 \mod 4$, utiliser l'exercice \ref{ex:racinecarree} pour un algorithme plus efficace. \end{enumerate} \end{exo} \begin{exo}[Proto-test de Fermat et nombres de Carmichael] \label{exTP:carmichael} \begin{enumerate} \item[] \item \'Ecrire un test de non-primalité basé sur le petit test de Fermat : $a^{p-1} = 1 \mod p$ pour tout entier $a \in \z$ premier à $p$ lorsque $p$ est premier. \item Faire la liste des entiers entre 1 et 5000 qui ne sont pas premiers mais pour lesquels le test renvoie vrai (on les appelle nombres de Carmichael). \item Majorer la complexité de cette recherche. \end{enumerate} \end{exo} \begin{exo}[Test de Miller--Rabin] \begin{enumerate} \item[] \item Programmer le test de Miller--Rabin. \item Vérifier qu'il détecte bien les nombres de Carmichael (cf. exercice \ref{exTP:carmichael}) comme non premiers. \item Pour $n=561$, trouver tous les entiers $a \in [1,560]$ qui passent le test de Miller-Rabin \end{enumerate} \end{exo} \begin{exo}[Certificat de primalité] Comprendre et détailler le certificat de primalité renvoyé par la commande Xcas ou PARI/GP \verb!isprime(9856989898997789789,1)! \end{exo} \end{document}