TER : algorithme Rho de Pollard pour le logarithme discret

Le sujet, sur le site du Master CSI.

Rapport

Le rapport se trouve dans le dossier rapport du répertoire. Essayons de le séparer en plusieurs fichiers .tex (un par chapitre semble raisonnable) pour faciliter la lisibilité et la rédaction.

# générer le rapport, sa TOC, sa bibliographie
cd rapport/
pdflatex main.tex
bibtex main
pdflatex main.tex
pdflatex main.tex

Soutenance

Le support pour la soutenance se trouve dans le dossier soutenance du dépôt.

# générer le rapport, sa TOC
cd soutenance/
pdflatex main.tex
pdflatex main.tex

Code

en C

On utilise la librairie GMP (documentation) pour manipuler de grands entiers.

# compiler l'éxécutable
cd c; make

# les nombres en entrée sont passés via `input.txt`
./pollard input.txt

# tests automatisés du code
cd c/test; make
./test_*

tester

# compiler les tests unitaires
cd c/test; make

# tester la fonction d'itération
./test_iteration

# tester plusieurs valeurs générées avec Sage
./bash_unit test/test_pollard_program.sh

mesurer

Nous souhaitons mesurer le nombre d'appels à la fonction d'itération pour la résolution d'un logarithme discret. Nous avons déjà des données calculatoires dans le fichier c/test/fixtures/inputs.txt. En lançant pollard sur ces données, on peut récupérer avec gprof le nombre d'appels à f, puis représenter tout cela sur un graphique.

cd graph
./generate_data.sh
python graph.py

avec Sage

cd sage