Efficacité
Nous travaillons sur le projet info de la factorisation par le crible
quadratique. Nous avons implemente le crible et le pivot et nous
arrivons a factoriser les nombres, mais meme en optimisant les
algorithmes nous n'arrivons pas a passer en-dessous de 3min50 pour F7 :
le programme est 10 fois trop lent. Est-ce que les temps de la page de
suivi ont ete obtenus a l'aide de cet algorithme ou il faut en
implementer un autre ?
Les temps indiqués sur la page de suivi sont là pour vous donner un
ordre de grandeur. Pour obtenir ces temps j'ai moi-même réalisé le
projet (en java). Même si je crois que mon implémentation suit bien
l'algorithme présenté, il y a quelques astuces.
Tout d'abord si votre programme fonctionne c'est l'essentiel, il semble
capable de factoriser T45. Je crois que c'est déjà pas mal.
Votre programme n'est pas dix fois trop lent, il est dix fois plus
lent que mon programme (enfin si vos machines sont à 1Ghz).
Mais, si on veut faire mieux...
Tout d'abord,j'ai écrit deux programmes indépendants pour le criblage et le
pivot, ce qui me permet d'éviter de remplir la mémoire de la machine
d'équations pendant le crible (ainsi, moins de coût de gestion
mémoire). Le crible produit les fichiers d'équations donnés sur la page de
suivi, le pivot les lit.
Je peux ainsi savoir facilement que le temps dominant est bien le criblage.
Ce qui semble indiquer que je n'ai pas à chercher optimiser le pivot
(qui est assez naïf). Si le pivot domine chez vous il faut aller y
voir.
Sinon, il faut accélérer le crible. Sans m'étendre, cribler ou non
selon les petits facteurs premiers semble avoir un certain impact sur
la performance, la taille de l'intervalle de criblage aussi. Il y a
d'autres astuces : notamment les tentatives de factorisation sont
effectuée en criblant, dès que la somme courante des log atteint une
limite fixée et la limite n'est calculée qu'une fois par intervalle...
Enfin, pour régler les divers paramètres (et surtout la
taille de l'intervalle de criblage) J'ai procédé à des essais.
Notez bien que parmi tout ce que j'ai raconté, je ne sais pas
ce qui explique réllement le facteur 10...