Remonter Suivant

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

Remonter Suivant