Projets M1 MIC 2019

Structure

Par binôme, rencontre toutes les semaines ou tous les 15 jours avec l'encadrant. il faut écrire un mémoire (~15 pages) et réaliser une implantation informatique, dont on fera une démonstration à l'oral.

Évaluation

Sujets proposés

  1. Factorisation des polynômes à coefficients entiers (Herblot)

    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é.

  2. Algorithme de Wiedemann (Molin)

    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.

  3. Factorisation ECM (Brasca)

    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.

    • Prime numbers (Crandall Pomerance)
    • Modern Computer Algebra, chapitre 19.
  4. Logarithme discret par calcul d'indice (Herblot)

    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.

  5. Attaques sur RSA (Herblot)

    On recensera un certain nombre d'attaques arithmétiques (Wiener, Coppersmith,...) et on en fera des démonstrations.

  6. Comptage de points sur une courbe elliptique par l'algorithme de Schoof (Brasca)

    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.

  7. Algorithmes de multiplication (Brasca)

    On s'intéressera aux algorithmes de multiplication rapides d'entiers de grande taille.

    • Modern Computer Algebra, chapitre 8.
  8. Le problème du sac à dos (Brasca)

    étudier le problème du sac à dos, le cryptosystème associé, diverses attaques

  9. Chiffrement homomorphe (Molin)