\documentclass[a4paper,12pt]{amsart}
\usepackage{kbexo}

\course{MHT911 -- Master CSI}
\num{2}

\begin{document}
\exotitle
\exo En représentant les polynômes de $\ZM[X]$ des tableaux d'entiers,
programmer la multiplication $a \times b$ (algorithme naïf).

\exo En représentant les entiers $a,b>0$ par des tableaux de bits, programmer
la multiplication $a \times b$ (algorithme naïf). Tester la complexité
pratique.

\exo Programmer l'algorithme de multiplication de Karatsuba, appliqué
à deux entiers $0\leq a,b < B^n$, où $B = 2^{32}$. Pour le découpage
$a = a_1 B^{n/2} + a_0$, on pourra utiliser
\bprog
  a1 = a >@relax> (16*n);
  a0 = a - a1 <@relax< (16*n);
@eprog
\Q Tester la complexité pratique de votre implantation.
\Q Que se passe-t'il si on remplace les expressions ci-dessus par les
définitions plus naturelle
\bprog
  N = 2^(16*n); a1 = a \ N; a0 = a % N;
@eprog

\exo \kbd{Mod(a,N)} est un constructeur pour la classe de congruence
$a\in\ZM/N\ZM$. 

\Q Évaluer la complexité pratique des opérations $+,-,\times,/$ dans
$\ZM/N\ZM$ (en fonction de la taille de $N$).

\Q La fonction \kbd{gcd} calcule un pgcd et \kbd{gcdext} une relation de
Bezout.
\qq Comparer leurs complexité pratique.
\qq Estimer expérimentalement la probabilité que deux entiers dans $[0,X]^2$
soient premiers entre eux (quand $X\to\infty$).

\Q Écrire un programme retournant un vecteur contenant les éléments
inversibles de $\ZM/N\ZM$.

\Q\hint{Réduction paresseuse}. Écrire une fonction calculant le produit
scalaire de deux vecteurs de $(\FM_p)^n$; tester là avec des vecteurs
de \kbd{t\_INTMOD}s, puis avec des vecteurs d'entiers en réduisant le
résultat \emph{final} modulo $p$.

\exo

\Q Programmer les tests de non-primalité de Miller-Rabin et Solovay-Strassen.
La fonction \kbd{kronecker(a,b)} calcule le symbole de Jacobi
$\leg{a}{b}$.

\Q Pour un entier impair $N$ non premier, calculer le nombre de faux-témoins
pour l'un et l'autre test. Essayer plusieurs valeurs de $N$, en particulier
$N = 561$. (On doit atteindre sans problême des valeurs de l'ordre de $10^6$.)
\end{document}
