L'algorithmique de la factorisation sur Z[x] met en jeu la factorisation modulo p, et des problèmes de relèvement à Z. Le but est d'écrire un algorithme complet et d'évaluer sa complexité.
On cherche à résoudre des systèmes linéaires Ax=b en (très) grande dimension sur un corps fini. La technique de Wiedemann passe par le calcul du polynôme minimal de A, obtenu via une utilisation ingénieuse de la théorie des suites récurrentes. On étudiera et programmera l'algorithme.
ECM, ou elliptic curves method, est une généralisation de la méthode de factorisation p-1, extrêmement efficace et très utilisée. On programmera la méthode (phases 1 et 2) et on l'utilisera pour déterminer des facteurs d'entiers de Fermat ou de Mersenne.
Il s'agit de la méthode la plus efficace pour résoudre le logarithme discret. Il en existe de multiples variantes, on programmera l'algorithme dans sa forme simple, assez similaire au crible quadratique.
On recensera un certain nombre d'attaques arithmétiques (Wiener, Coppersmith,...) et on en fera des démonstrations.
On s'intéressera au calcul du cardinal d'une courbe elliptique sur un corps fini, à l'aide de méthodes génériques de type pas de bébé pas de géant, puis on étudiera l'algorithme de Schoof.
On s'intéressera aux algorithmes de multiplication rapides d'entiers de grande taille.
étudier le problème du sac à dos, le cryptosystème associé, diverses attaques