Ce depot contient le rapport du projet encadré de recherche co-rédigé par Axel Durbet, Fivos Reyre et Sid Ali Zitouni Terki au 2eme semestre de la première année du Master CSI de Bordeaux.

1. Introduction
2. Pré-requis théoriques

• Arithmétique de base
• Anneaux et corps fini

3. Test de primalité

• Test combinatoire
• Test de fermat
  • Algorithme
  • Probabilité d'erreur
• Test de Miller-Rabin
  • Algorithme
  • Probabilité d'erreur
• Comparaison
• AKS

4. Méthodes élémentaires de factorisation

• Premières idées
• Puissance d'un nombre premier
• Variante du crible d'Eratosthène
• Remarque sur l'indicatrice d'Euler

5. Trois algorithmes de factorisation

• Algorithme de p-1 de Pollard
• Méthode de p+1 de Williams
• Courbes elliptiques
  • Définitions et théorèmes
  • Algorithme de Lenstra

6. Analyse de Complexité

• Complexité
  • La notation L
  • L et la friabilité
  • Le choix de B dans les courbes elliptiques

7. Implémentation
8. Conclusion