La factorisation c'est une conséquence d'un algo de réduction de réseau.
Si j'ai bien pigé, il utilise une hypothèse qui n'est pas toujours vérifiée (Geometrical Series Assumption), donc ça ne marche que "presque tout le temps" (mais en pratique je suppose que ça sera un détail).
L'algo, il l'avait déjà donné (peut être là? http://www.springerlink.com/content/p3511w638h45616u/fulltext.pdf ); dans son exposé il montre que c'est polynomial.
Je ne sais pas s'il y a une implémentation.