Previous Up

Vos questions (et mes réponses)

Précisions sur l'algorithme


Nous nous demandons comment factoriser les yi sur la base des pi:
 
La case w8 attire l'attention, on a d'une part w8 = 10 et d'autre part
log2(y8) ? 12 (y8 = 2141). L'entier y8 est sans doute un produit de
facteurs de la base +(de fait ici on sait que y8 est divisible par 2 ?
3 ? 7 ? 17 et que le quotient +est proche de 22), on lance une
tentative de factorisation de y8 sur la base de +facteurs. Il vient :
1252 ? 2 ? 32 ? 7 ? 17 (mod n )
 
Nous avons tout d'abord pensé à stocker dans une matrice W' les pi qui
interviennent dans la composition des xi et sauvegardé ansi les
différentes +étapes du crible. Cependant, cela ne fait que repousser
le problème en +descendant les ordres en pi d'un degré.  Nous avons
pensé à tester tous les pi à l'aide de la division euclidienne, mais
nous ne sommes pas sûrs que Z/nZ soit un anneau euclidien. Nous
pensons même le +contraire.
  
Comment réaliser la factorisation de y, sans réutiliser un crible?
Pour le crible et la factorisation sur la base, on ne raisone pas modulo n.

Le polynôme de Kraitchick donne des equations xi2 = yi (modulo n) avec bien évidemment xi2 ≠ yi (NB on effectue le calcul dans Z), ainsi dans l'exemple on a par exemple 113 × 113 − 13483 = −714, et ainsi, par construction, nous savons que 1132 est congru à −714 (modulo n)

On cherche ensuite à factoriser yi comme un entier banal sur la base de facteurs (dans le but ultime de trouver une congruence de carrés non triviale) . Le crible permet d'aller plus vite en identifiant les yi pour lesquels il vaut la peine d'essayer l'algorithme simple par divisions successives selon les nombres premiers de la base.

L'algo le plus simple consiste à diviser y, le yi sélectionné, par les facteurs croissants f de la base. On arête tout quand y vaut 1 (et alors il y a succès) ou quand on a épuisé les facteurs de la base (et alors il y a échec).

C'est une description rapide il y en a une plus précise en ici (section 2).

Notes finales :
  1. Si y est négatif initialement alors on factorise −y (en enregistrant un facteur −1).
  2. La base de facteur ne contient pas nécessairement tous les nombre premiers jusqu'à la limite B, seulement ceux d'entre eux pour lesquels il existe des racines de x × x − n (modulo f). En effet, supposons qu'il n'y a pas de telles racines cela veut dire que pour tout x, x2−n n'est pas divisible par f. Or y est justement de la forme x2−n pour x = xi donné.

    Bref, tout ceci pour dire qu'il ne sert à rien d'essayer de diviser y par les f tels qu'il n'y a pas de racine de x2−n (modulo f) : la division ne tombe jamais juste.

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

Déroulement de l'oral


Pour la soutenance du projet info, sommes censés faire quoi exactement
(démos, powerpoint ou pas, partage du temps...) ?
Pour moi l'essentiel est de démontrer que vous avez résolu le problème posé et d'expliquer comment. Plus de détails ici.
Previous Up