\NeedsTeXFormat{LaTeX2e}
\documentclass[10pt,a4paper,twoside]{amsart}
\usepackage{amsmath,amsfonts,amssymb,latexsym}
\usepackage{a4,mathptmx,helvet,courier}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\newcounter{exonum}[section]
\newenvironment{exo}{\begin{enumerate}\stepcounter{exonum}%
\renewcommand{\theenumi}{\thesection.\arabic{exonum}}%
\renewcommand{\labelenumi}{\bf\theenumi.}\item}{\end{enumerate}}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\textheight 20cm

\begin{document} 

\pagestyle{empty}
\thispagestyle{empty}


{\footnotesize\noindent
Université Grenoble Alpes   \hfill $\bullet$ \hfill
Licence2, mat309                       \hfill $\bullet$ \hfill
Année 2019/2020           \\[-2mm]\hrule}

%\bigskip

\begin{center}
 Examen du 24 juin 2020, \`a faire en 2 heures dans les
conditions d'un examen surveill\'e.\\
\`A rendre au plus tard le 25 juin \`a 8h30 dans Travaux sur~:\\
\verb|https://chamilo.univ-grenoble-alpes.fr/courses/GBX3MT39/|\\
%Ce sujet comporte 2 exercices sur {\bf 1 page}.\\
  {\it 
Plusieurs questions sont individualis\'es avec votre num\'ero
de carte d'\'etudiant, not\'e $E$.
\\
Le sujet comporte 2 pages. Le barême est indicatif.\\
Toutes les r\'eponses doivent \^etre justifi\'ees!}
  
\end{center}

\section{Congruences (3 points)}
Soit $a$ l'entier form\'e par les 4 premiers chiffres de votre
num\'ero d'\'etudiant $E$ et $b$ celui form\'e par les 4 derniers chiffres.
D\'eterminer un entier $c$ compris entre 1 et 276740 tel que
$c-a$ soit divisible par 137 et $c-b$ soit divisible par 2020.
On donnera le d\'etail des calculs.

\vspace{0.1cm}

\section{Puissance modulaire (6 points)}
\begin{enumerate}
\item Expliquer comment on peut v\'erifier si $2027$ est premier.
Attention, on ne demande pas de faire tous les calculs n\'ecessaires,
mais d'indiquer quels calculs il faut faire.
\item Votre num\'ero d'\'etudiant $E$ est-il inversible modulo 2027~?
Si oui d\'eterminer son inverse $i$.
\item Calculer le reste $r$ de la division de $E^{2020}$ par 2027 par
la m\'ethode de la puissance rapide. Combien de divisions doit-on
effectuer~?
\item Lorsque $E$ admet un inverse $i$, exprimer $r$ en
fonction d'une puissance de $i$. Cette m\'ethode de calcul vous
semble-t-elle plus efficace que la pr\'ec\'edente~? Justifier.
\end{enumerate}

\vspace{0.1cm}

\section{Preuve par 9 et par F (11 points)}
Dans cet exercice, on travaille avec des entiers positifs.
\subsection{Preuve par 9}
Pour tester si le produit de deux entiers \'ecrits en base 10 est
correct (sans calculatrice), on peut utiliser une m\'ethode appel\'ee
{\bf preuve par 9}
d\'ecrite ci-dessous. \\
On d\'efinit pour cela une fonction $f$ sur les entiers
et \`a valeur dans les entiers de 1 \`a 9 de la mani\`ere suivante~:
si $a=0$, on pose $f(0)=9$ ; si $a$ est un entier strictement positif \'ecrit en
base 10, on calcule la somme de ses chiffres, 
et on recommence jusqu'\`a obtenir un entier compris entre 1
et 9 que l'on note $f(a)$. \\
Exemple 1~: si $a=12345$, alors $1+2+3+4+5=15$ puis $1+5=6$ donc
$f(a)=6$. \\
Exemple 2~: si $b=670$, alors $f(b)=f(6+7+0)=f(13)=4$. \\
On observe alors
que $ab=8271150$, $f(ab)=f(24)=6$ et $f(f(a)f(b))=f(6 \times 4)=6$
sont \'egaux.
\begin{enumerate}
\item Soit $q$ et $r$ le quotient et le reste de la division
  euclidienne de $E$, votre
num\'ero de carte d'\'etudiant, par $10^5$.
D\'eterminer $f(q)$ et $f(r)$.
\item Pour $k$ entier, d\'eterminer la classe de $10^k$ dans $\mathbb{Z}/9\mathbb{Z}$.
\item Soit $a$ un entier, comparer les classes de $a$ et $f(a)$ dans $\mathbb{Z}/9\mathbb{Z}$.
\item Soient $a$ et $b$ deux entiers, d\'eterminer $f(ab)$ en fonction
  de $f(a)$ et de $f(b)$. 
\item Si $f(c) \neq f(f(a)f(b))$, peut-on en d\'eduire que $c \neq ab$~?
Si $f(c)= f(f(a)f(b))$, peut-on en d\'eduire que $c=ab$~?
\item Comparer $f(E)$ et $f(q+r)$. Est-ce toujours vrai~? 
\item Donner un programme C ou Python 
ou un algorithme en langage naturel
pour calculer $f(a)$.
\end{enumerate}

\subsection{Preuve par F}
On veut adapter la m\'ethode pr\'ec\'edente pour v\'erifier le produit
de deux entiers \'ecrits en base 16, les chiffres sont donc compris
entre 0 et F (quinze). On calcule $g(a)$ en faisant la somme des
chiffres de $a$ en base 16 et en recomman\c{c}ant jusqu'\`a
obtenir un entier compris entre 1 et F (quinze).
\begin{enumerate}
\item D\'eterminer l'\'ecriture des entiers
$q$ et $r$ de la question 3.1.(1) en base 16.
\item 
D\'eterminer $g(q)$ et $g(r)$.
\item Soient $a$ et $b \in \mathbb{N}^*$. 
Comparer $g(ab)$ et $g(a)$ et $g(b)$.
\item A-t-on $g(E)=g(q+r)$~? Pourquoi~?
\item Comment faut-il adapter l'algorithme de calcul de $f$ pour
  calculer $g$~?
\item Peut-on g\'en\'eraliser la preuve par 9 ou par F 
\`a une base $b$ quelconque~? Si oui, comment~?
\end{enumerate}

\vspace{1cm}

Fin du sujet. \`A rendre au plus tard le 25 juin \`a 8h30 dans Travaux sur~:\\
\verb|https://chamilo.univ-grenoble-alpes.fr/courses/GBX3MT39/|\\

\end{document}
\vspace{0.5cm}

\section{Codage (4 points)}
On consid\`ere un code lin\'eaire de matrice \`a coefficients modulo 2:
$$
A=\left(
\begin{array}{cc}1&0\\0&1\\1&0\\1&0\\0&1\\0&1\\1&0\\1&0\\0&1\\0&1\end{array}
\right)
\pmod 2
$$
\begin{enumerate}
\item Quel est la distance de Hamming de ce code~?
\item En d\'eduire $t$, le nombre maximal d'erreurs qu'on peut esp\'erer corriger.
\item Donner une m\'ethode simple pour corriger au plus $t$ erreurs.
\item Discuter l'efficacit\'e de ce code par rapport \`a un code de r\'ep\'etition.
\end{enumerate}

\vspace{0.5cm}

\section{Racine primitive}
\begin{enumerate}
\item Expliquer comment on peut v\'erifier que $p=12289$ est premier.
Attention, on ne
demande pas de faire tous les calculs n\'ecessaires, et on admettra
dans la suite sans avoir fait toutes les v\'erifications que 12289 est premier.
\item Toujours pour $p=12289$, v\'erifier avec l'algorithme
  d'exponentiation rapide que
$$ 11^{1024} = 79 \ [p] $$
11 est-il un g\'en\'erateur de $(\Z/p\Z)^*$~?
\item Toujours pour $p=12289$, 
d\'eterminer un entier $z$ tel que 
$$
z^{(2^{12})}=1 \ [p], \quad z^{(2^{11})} \neq 1 \ [p] 
\quad (*)
$$
Indication~: chercher $z$ sous la forme d'une puissance de 11 bien choisie.
\item 
Montrer que si un couple $(z,p)$ 
v\'erifie (*) avec $p$ premier alors $p$ 
est de la forme $p=k2^{12}+1$ pour $k$ entier.
\item 
Les couples d'entiers $(z,p)$ v\'erifiant une propri\'et\'e analogue
\`a (*) sont tr\`es utiles pour impl\'ementer des
algorithmes  de multiplication rapide de polyn\^omes utilisant
la FFT (Fast Fourier Transform). On souhaite en g\'en\'erer
automatiquement.\\
On suppose qu'on dispose d'une fonction 
\verb|isprime(n)| qui renvoie un bool\'een
vrai si $n$ est premier. \'Ecrire un algorithme \verb|premiers(n,t)|
renvoyant la liste des \verb|n| nombres premiers $p$
les plus petits possibles qui sont de la forme $k2^{t}+1$.\\
Bonus~: Adapter l'algorithme pour trouver des couples $(z,p)$
v\'erifiant
$$ z^{(2^t)}=1 \ [p], \quad z^{(2^{t-1})} \neq 1 \ [p]  $$
\end{enumerate}

\vfill


%\pagebreak

\end{document}

\vspace{0.5cm}

\section{Multiplication}
\begin{enumerate}
\item
Montrer qu'on peut calculer le produit de deux nombres complexes
$$
(a+ib)(c+id)=(ac-bd)+i(ad+bc) \quad (*)
$$
en effectuant 3 multiplications de r\'eels au lieu de 4
(on pourra d\'evelopper $(a+b)(c+d)$ ou $(a+b)(c-d)$).
Combien d'additions sont-elles n\'ecessaires~?
\item Si $a,b,c,d$ sont des entiers ayant $n$ chiffres avec
$n$ tr\`es grand, estimer le rapport entre le temps
que mettra un algorithme utilisant cette m\'ethode par
rapport \`a la m\'ethode naive consistant \`a appliquer 
(*). Justifier votre estimation.
\item
Montrer qu'on peut calculer le carr\'e d'un nombre complexe
en effectuant 2 mutiplications de r\'eels.
Estimer le gain de temps qu'on peut attendre d'une telle m\'ethode
si on calcule le carr\'e d'un nombre complexe de la forme $a+ib$
avec $a$ et $b$ des entiers ayant un tr\`es grand nombre de chiffres.
\end{enumerate}

\section{Secret partag\'e.}
Deux personnes, Alice et Bob, souhaitent avoir un secret partag\'e
(par exemple pour \'echanger des informations crypt\'ees avec
un algorithme \`a clef secr\`ete).
Pour cela, elles choisissent deux entiers $m,n$ qui sont publics, et 
chacun une clef secr\`ete
