Meilleurs algorithmes de factorisation des nombres premiers

Introduction

Il existe plusieurs points communs entre l'algorithme GNFS de factorisation des nombres semi premiers et l'algorithme knapsack :

• La factorisation (via les logarithmes) et le sac à dos (knapsack) utilisent tous deux des combinaisons additives de « poids ».
• L’algèbre linéaire mod 2 du GNFS constitue un sous-problème de type sac à dos.

Limites :
• La factorisation n’est pas NP‐complète au sens classique, et on ne connaît pas de réduction en temps polynomial vers le problème du sous-ensemble (subset-sum).
• Tenter un subset-sum sur les bits ou sur ln⁡(p) reste de complexité Ω (√N).

Vraie puissance :
• Les algorithmes de factorisation les plus performants (GNFS, ECM) exploitent des méthodes de crible et de réseaux, dont la phase de combinaison linéaire ressemble à un knapsack mod 2, mais ils s’appuient sur une structure mathématique bien plus riche.

L’analogie avec le sac à dos met en lumière le caractère combinatoire de la factorisation, sans pour autant lever la difficulté intrinsèque de parcourir un espace de taille ≈√N.

Fonctionnement de l'algorithme GNFS

Le GNFS fonctionne en deux grands compartiments :

1. Phase de collecte (crible) : repérage de suffisamment de (a,b) tels que les deux projections (rational et algebraic) soient lisses sur le même petit ensemble de premiers.
2. Phase de combinaison (algèbre linéaire + square root) : exploitation de relations linéaires entre exposants mod 2 pour produire un carré modulo N, puis extraction d’un facteur non trivial par gcd⁡.

Sur de très grands entiers (1024 bits et plus), c’est l’algorithme qui surpasse tous les autres en pratique (hors cas très particuliers), avec une complexité heuristique en :

C’est pourquoi toutes les dernières avancées en cryptanalyse RSA de grande taille reposent, directement ou indirectement, sur le General Number Field Sieve.

Ou trouver le meilleur code pour faire fonctionner l'algorithme ?

Voici quelques-unes des implémentations les plus abouties et maintenues du GNFS :

1. CADO-NFS
C’est l’implémentation de référence en C/C++ du GNFS, développée par l’équipe CADO-NFS (INRIA & co.). Elle couvre toutes les phases du NFS (sélection de polynôme, crible, filtrage, algèbre linéaire, racine carrée) et peut être distribuée sur un réseau.
On y accède via :
GitLab (INRIA) : https://gitlab.inria.fr/cado-nfs/cado-nfs GitLab
GitHub miroir : https://github.com/cado-nfs/cado-nfs GitHubGitHub
Documentation et téléchargements sur : http://cado-nfs.inria.fr/ CADO-NFS

2. Msieve / GGNFS
Msieve est un logiciel de factori¬sation très populaire qui inclut un module GNFS (GGNFS). Il est écrit en C et propose à la fois le crible et l’algèbre linéaire (avec l’algorithme skeleton de D. Bernstein et tuxpe), plus un résumé pour l’étape « square root ».
Dépôt GitHub : https://github.com/radii/msieve
Documentation & binaire précompilé disponibles sur le même repo.

3. GGNFS standalone
Le projet « GGNFS » correspondant à la seule partie GNFS (sans msieve) existe aussi sous forme autonome, mais la plupart des utilisateurs préfèrent la version packagée dans Msieve ou CADO-NFS.

Pourquoi privilégier CADO-NFS ou Msieve ?

• CADO-NFS
Couvre l’ensemble des étapes du GNFS (sélection de polynôme de Kleinjung, optimisations récentes, crible à large bande, filtrage, algèbre linéaire distribuée, racine carrée…).
Très utilisé pour les records de factorisation (ex. RSA-704, RSA-768, etc. eprint.iacr.org).
Bien documenté (tutoriels PDF, wiki, listes de diffusion), et constamment mis à jour par INRIA et la communauté.

• Msieve
Plus léger si vous voulez juste le moteur GNFS sans l’infrastructure de CADO-NFS.
Permet de choisir différents back-ends d’algèbre linéaire (Jacobi, Block Lanczos, Block Wiedemann).
Souvent utilisé comme référence pour des factorisations de taille “moyenne” (jusqu’à ~200 chiffres).

Où trouver la documentation et les exemples d’usage ?

• CADO-NFS
Tutoriels PDF (ex. “Factoring integers with CADO-NFS” par Jérémie Detrey) : https://www.ens-lyon.fr/LIP/AriC/wp-content/uploads/2015/03/JDetrey-tutorial.pdf ens-lyon.fr
Wiki & paramètres de tuning : http://cado-nfs.inria.fr/wiki/

• Msieve / GGNFS
README du dépôt GitHub : https://github.com/radii/msieve
Options de ligne de commande (sélection de polynôme, crible, filtrage, etc.) décrites dans ce même README.

En résumé, pour obtenir le “meilleur code” GNFS :

• CADO-NFS (INRIA) est la référence pour de très grandes factorisations (> 200 chiffres), avec un support actif et toute la chaîne GNFS.
• Msieve/GGNFS est plus léger si vous souhaitez juste un exécutable GNFS autonome, mais il requiert parfois des ajustements manuels des paramètres.
Tous deux sont libres (LGPL pour CADO-NFS, licence publique pour Msieve) et disponibles sur GitLab ou GitHub.