Factorisation par la méthode du crible quadratique

1  Factorisation des grand nombres

La factorisation effective d’entiers toujours plus grands, que l’on pouvait autrefois qualifier d’amour de l’art, voire de hobby (mais aussi d’effort de recherche fondamentale), connaît des applications médiatisées en cryptographie, car la sécurité des systèmes de cryptage modernes semble bien reposer en dernière analyse sur la difficulté de répondre à cette question toute bête : Soit ce nombre n, dont je sais qu’il n’est pas premier, quels sont ses facteurs ?

Dans ce projet nous allons aborder une méthode de factorisation qui a fait date. La méthode du crible quadratique est une introduction aux méthodes générales de factorisation modernes, qui en sont souvent des raffinements. Par ailleurs, le crible quadratique s’appuie sur des concepts raisonnablement simples de la théorie des nombres, ce qui place sa mise en œuvre à notre portée.

2  Principe

La méthode de factorisation repose sur une idée assez ancienne (1920) du mathématicien Maurice Kraitchick. Soit n un entier que nous souhaitons factoriser. Supposons que, par un moyen quelconque, nous connaissons deux autres entiers X et Y, tels que X² ≡ Y² (mod n ) soit vrai, Il existe donc un entier k tel que (X−Y)(X+Y) = k n. Avec un peu de chance, X−Y et n ont des facteurs non triviaux en commun et pgcd(X−Y, n) est un facteur de n. (en cas de malchance on essaie une autre congruence). Cette idée est un raffinement d’une autre, encore plus ancienne, et due à Pierre de Fermat : pour factoriser n on peut essayer de l’exprimer comme la différence de deux carrés n = X² − Y² (et donc n = (X−Y)(X+Y)). Pour dire toute la vérité, la méthode de Kraitchick ne fonctionne que si n peut s’écrire comme produit de deux facteurs premiers entre eux, c’est-à-dire si n n’est pas une puissance (et n’est pas premier bien évidemment). Ce n’est pas bien grave.

En ce qui nous concerne, la supériorité de l’idée de Kraitchick tient à ce qu’on peut trouver ses deux fameux entiers X et Y pour un prix plus modique que ceux de Fermat. On peut en effet procéder ainsi :

1. Définir les petits nombres premiers en considérant les nombres premiers inférieurs à un certain entier B. On note p₁, p₂, …, p_b les petits nombres premiers, que l’on complète par p₀ = −1 pour pouvoir factoriser des entiers négatifs.
2. Chercher les entiers x_i tels la décomposition en facteurs premiers de y_i = x_i² − n s’écrit uniquement à l’aide de petits nombres premiers. Un tel y_i est dit B-régulier. On obtient ainsi des congruences de la forme x_i² ≡ p₀^{α_{0, i}} p₁^{α_{1, i}} ⋯ p_b^{α_{b, i}} (mod n ) (on peut toujours poser α_k,i = 0 si p_k ne divise pas y_i). Pour augmenter la possibilité de trouver des y_i B-réguliers, on essaie les y_i à priori petits, en prenant les x_i voisins de √n.
3. Multiplier membre à membre certaines des équations de l’étape précédente afin d’obtenir une égalité X² = Y² modulo n. Il n’y aucun problème pour obtenir le carré X² (c’est le produit de certains x_i). Pour obtenir le carré Y², on utilise les décompositions en petits facteurs premiers, en sélectionnant les équations de sorte que la somme des α_{k, i} soit paire pour tous les k.

Un exemple simple illustrera la méthode, cherchons à factoriser le nombre n = 13483. Un peu au hasard nous choisissons B = 20. On sélectionne ensuite des valeurs du polynôme P(x) = x² − n (dit polynôme de Kraitchick) qui sont B-régulières, pour x voisin de ⌊√n⌋ = 116. On aura ainsi par exemple, les équations (modulo n) :

(On notera la présence de −1, due à des valeurs de x_i inférieures ou égales à ⌊√n⌋.)

En multipliant toutes les équations sauf la seconde entre elles on obtient :

Soit encore X ≡ 8265 (mod n ) et Y = 2² · 3³ · 7³ · 17² ≡ 13269 (mod n ). Au final, on calcule pgcd(8265 − 13269, n) qui vaut 139. Et effectivement on a bien n = 139 · 97.

Pour rendre la méthode de factorisation décrite effective, il faut résoudre deux questions.

• Trouver des congruences x_i² ≡ p₀^{α_{0, i}} p₁^{α_{1, i}} ⋯ p_b^{α_{b, i}} (mod n ) efficacement, car la méthode évidente d’essai de division des y_i par les petits nombres premiers est bien trop coûteuse. On procédera selon la technique du crible quadratique introduite en 1982 par Carl Pomerance.
• Combiner les congruences de l’étape précédente pour obtenir des congruences finales X² ≡ Y² (mod n ). C’est possible, à l’aide d’un peu d’algèbre linéaire sur l’espace vectoriel (ℤ/2ℤ)^k, noté à l’américaine F₂^k.

3  Le crible quadratique

Le crible quadratique est une genéralisation du crible d’Eratosthène. En effet, pour tout polynôme P(x) et tout entier p nous avons P(x) ≡ P(x + p) (mod p ). Soit, supposant connu x_a tel que P(x_a) ≡ 0 (mod p ), nous pouvons rapidement conclure que P(x_a+p), P(x_a+2p), …, P(x_{a+ℓ p}), … sont divisible par p (dans le crible d’Eratosthène, on a P(x) = x et x_a = p). En combinant ces parcours de p en p pour divers facteurs premiers, nous allons identifier des P(x) qui sont B-réguliers.

On considère donc une base de facteurs p₀, p₁, …, p_b (p₀ = −1, p₁ = 2, etc.) en supposant bien évidemment que n n’est divisible par aucun des « vrais » p_k (auquel cas nous connaîtrions un facteur de n). Cette base ne regroupe pas tous les nombres premiers inférieurs à B. En effet, il n’y a pas nécessairement de racine modulo p de l’équation P(x) = 0 pour p quelconque. Nous supposons donc que la base de facteurs regroupe les petits nombres premiers tels que P(x) a des racines modulo p_k. Dans le cas du polynôme de Kraitchick (qui est quadratique) et pour un p_k (k ≥ 1) donné, il y aura une ou deux solutions. Pour p₁ = 2, par hypothèse n impair, nous avons une seule solution qui est x ≡ 1 (mod 2 ). Pour tout autre p_k premier, il y a deux solutions (car n n’est pas divisible par p_k) qui sont d’ailleurs opposées modulo p_k, et notées r_k et r′_k. Par exemple, dans le cas n = 13483, B=20 la base de facteurs se restreint à −1, 2, 3, 7, 17 avec r₁ = 1, r₂ = 1, r₃ = 1 et r₄ = 6 (et aussi r′₂ = 2, r′₃=6, r′₄=11).

Étant donnée une taille T et une valeur initiale x₀ nous considérons l’intervalle [x₀… x₀+T[ d’entiers notés x₀, x₁, … x_T−1. Dans le même esprit nous posons y_i = P(x_i). Soit encore un tableau w d’entiers w_i valant initialement zéro. Pour un p_k donné nous pouvons détecter tous les y_i multiples de p_k et enregistrer ce fait dans le tableau w. Il suffit de calculer x₀ mod p_k et d’en déduire x_a et x_a′, racines de P(x) = 0 modulo p_k telles que a et a′ sont minimaux (pour k=1 on a a = a′). Ensuite, on parcourt le tableau w de p_k en p_k à partir de a et de a′, en ajoutant le logarithme de p_k aux w_i ainsi repérés. En pratique, on utilise une approximation entière du logarithme de base 2, qui conduit à des calculs peu coûteux. Une fois ce parcours effectué on applique l’algorithme de factorisation par division des facteurs de la base aux y_i pour lesquels w_i est suffisamment proche du logarithme de y_i. On obtient ainsi une nouvelle équation x_i² = … presqu’à coup sûr.

Dans notre exemple, posons T=32 et criblons à partir de x₀ = 117. Le nombre x₀ est impair, comme r₁, on a donc a=0. Après un premier passage le tableau w est donc

Considérons maintenant le passage pour p_k = 3. On a x₀ mod 3 =0, r₂ = 1, r′₂ = 2, et donc a = 1 et a′ = 2. En approximant log₂(3) par 2 et en criblant, il vient :

Il reste à effectuer le criblage des multiples de 7 (log₂(7) ∼ 3) et de 17 (log₂(17) ∼ 4). On obtiendra alors les états successifs du tableau w.

La case w₈ attire l’attention, on a d’une part w₈ = 10 et d’autre part log₂(y₈) ∼ 12 (y₈ = 2141). L’entier y₈ est sans doute un produit de facteurs de la base (de fait ici on sait que y₈ est divisible par 2 · 3 · 7 · 17 et que le quotient est proche de 2²), on lance une tentative de factorisation de y₈ sur la base de facteurs. Il vient :

On notera que le décalage entre w₈ et log₂(y₈) peut s’expliquer ici parce que nous n’avons pas pris la peine de cribler selon les puissances des facteurs de la base, mais qu’il provient aussi dans le cas général de l’usage d’une approximation entière du logarithme.

Le crible s’applique en fait à des nombres plus grands que la valeur de n donnée en exemple. Il se révèle alors très efficace pour repérer les nombres B-réguliers, à condition de considérer attentivement certains points.

• Un bon choix du paramètre B est fondamental, C. Pomerance recommande B de « l’ordre de » L(n)^1/2, avec :

  L(n) = e

  ⎛ ⎝ ln(n) · ln(ln(n)) ⎞ ⎠ 1 2

  Le temps calcul théorique est alors de l’ordre de L(n).

• Le logarithme de base deux des y_i s’approxime facilement comme le nombre de bits utilisés dans l’écriture en base deux. Cette quantité se calcule aisément à partir de la représentation machine des entiers (et la bibliothèque de calcul des grand nombres BigInteger la propose).
• La décision de voir le crible comme un moyen de trouver des y_i probablement B-réguliers (avant de vérifier) autorise de nombreuses économies. Nous avons vu que l’on peut se passer de cribler selon les puissances des facteurs de la base. On peut aussi envisager de se passer du criblage par les plus petits facteurs de la base, dont la contribution aux w_i peut être négligée et dont le criblage est coûteux. Quoiqu’il en soit, le bon choix des nombres à tenter de factoriser effectivement est critique. La condition w_i ≥ log₂(y_i) − log₂(B) est un bon point de départ.
• Il faut produire suffisamment d’équations pour garantir l’obtention de plusieurs congruences de carrés X² ≡ Y² (mod n ). En pratique, comme nous allons le voir, si b+1 est le nombre d’entiers de la base de facteurs, b+1+m congruences mènent sûrement à m congruences de carrés. La probabilité qu’une congruence donne une factorisation triviale étant estimée à, au pire, 1/2, choisir m=10 nous donne une probabilité d’échec minime. Échec qui n’a d’ailleurs rien de définitif.
• La taille T des intervalles de criblage résulte d’un compromis entre le besoin d’amortir les calculs nécessaires pour démarrer le criblage sur un intervalle (par exemple, le recalage des progressions arithmétiques de taille p_k) et l’utilisation de la mémoire de la machine.

4  Algèbre linéaire

Après criblage, nous sommes donc en possession de (nombreuses) congruences x_i² ≡ p₀^{α_{0, i}} p₁^{α_{1, i}} ⋯ p_b^{α_{b, i}} (mod n ), que nous cherchons à multiplier afin de produire un carré à droite. Cela revient à trouver un ensemble I d’indices i tel que, pour tous les k, les sommes Σ_{i ∈ I} α_k,i sont paires. Cela revient de fait à trouver une famille liée dans l’espace vectoriel F₂^b+1.

À chaque congruence, associons un vecteur z^→i = (z₀ⁱ   z₁ⁱ   ⋯   z_b+1ⁱ) de F₂^b+1, avec z_kⁱ = α_k,i mod 2. Nous cherchons en fait l’ensemble I tel que Σ_{i ∈ I} z^→i = 0^→. Opérationnellement on cherche à démontrer que la matrice Z = (z_kⁱ) est singulière en exhibant une combinaison linéaire (somme sur F₂^b+1) de ses lignes qui soit nulle. L’algorithme classique du pivot de Gauss permet d’atteindre ce résultat (garanti dès que la matrice a plus de lignes que de colonnes). Considérons à nouveau notre exemple de la factorisation de 13483. En supprimant la seconde ligne, la matrice des parités des exposants possède 4 lignes de 5 colonnes, nous lui adjoignons une autre matrice T qui est la matrice unité 4 × 4.

L’opération de base du pivot consiste pour un k donné à annuler les z_kⁱ sauf pour un i donné, on y parvient par combinaison linéaire (ici somme) des lignes de Z avec une ligne i₀ telle z_k^i₀ n’est pas nul. Les combinaisons de lignes sont enregistrées dans les lignes de la matrice T. L’élément conservé est dit pivot. Si le nombre de lignes de Z dépasse celui de ses colonnes, on est sûr d’aboutir (à condition de prendre tous les pivots dans des lignes différentes). Ici choisissons d’abord d’éliminer les 1 de la première colonne, en prenant z₀¹ comme pivot. Il vient :

La troisième ligne de la matrice T₀ est la somme des deuxième et troisième lignes de T : elle nous dit comment obtenir cette troisième ligne de Z₀ à partir de Z.

On choisit ensuite le pivot z₁⁰ (dans Z₀).

Prenons enfin le pivot z₂² :

On voit bien ici que la quatrième ligne de T₂ s’obtient comme la somme des deux dernières lignes de T₁. Elle nous dit toujours comment la quatrième ligne de Z₂ s’obtient en sommant certaines des lignes de la matrice Z de départ (ici toutes). Notons qu’un pivot de Gauss traditionnel échange les lignes des matrices, (afin de systématiquement placer le pivot en z_k^k), ce qui nous donnerait ici :

Les échanges de lignes dans Z sont aussi effectués dans T. Ainsi, rien ne change à la lecture que nous faisons des lignes de T comme exprimant des sommes de lignes de la matrice Z de départ.

L’implémentation efficace du pivot de Gauss dans notre cas particulier repose sur deux remarques.

1. On peut représenter les lignes des matrices Z et T comme des vecteurs de bits (classe BitSet de java). La sommation est alors l’opération « ou exclusif ».
2. Les matrices produites par le crible sont creuses, dans le sens qu’elles contiennent bien plus de 0 que de 1. Cette propriété autorise des spécialisations du pivot de Gauss, décrites dans [1] (fourni dans les documents complémentaires).

5  Travail demandé

Réaliser un programme Qs qui prend comme argument un nombre n adapté (n n’a pas de petit facteurs et possède au moins deux facteurs premiers distincts) et produit une factorisation de n. Par exemple :

# java Qs 350243405507562291174415825999
75576435361433 * 4634293795844903

Il s’agit d’un exemple « facile » dont la factorisation est quasi instantanée. La page de suivi donne d’autres exemples. En particulier, la factorisation du septième nombre de Fermat, F₇ = 2¹²⁸ + 1, exploit mondial dans les années 70 est largement à notre portée (elle peut prendre moins d’une minute).

Une répartition possible du travail dans le binôme est évidemment entre crible et pivot de Gauss. Attention, toutefois, il faut se rendre compte que, pour les tailles de nombres que nous traitons (pas plus de soixante chiffres), la réalisation d’un pivot de Gauss très optimisé semble moins critique que celle d’un crible efficace.

On utilisera donc les classes BigInteger et BitSet. Ces classes fournissent toutes les opérations de base dont vous aurez besoin à l’exception des « racines carrées » entières et modulo p. Je fournis (sur la page de suivi) le code nécessaire, afin que vous puissiez vous concentrer sur la programmation de l’algorithme (plus que sur la théorie des nombres, certes fascinante). L’objectif à atteindre est la factorisation de nombres d’environ soixante chiffres en quelques heures.

6  Prolongements possibles

Vous pouvez par exemple :

1. Proposer un programme de factorisation pratique qui s’applique aux entiers quelconques, on intégrera par exemple des tests de primalité, l’algorithme de division voire l’algorithme dit ρ de Pollard. Il faudra aussi détecter les puissances. Un bon point de départ pour aborder les algorithmes nécessaires est certainement [2] (à la bibliothèque).
2. Accélérer significativement votre crible. Vous pouvez commencer par déterminer si il vaut la peine ou pas de cribler selon les puissances des facteurs de la base, puis raffiner l’algorithme. Les méthodes sont nombreuses (polynômes multiples, distribution du criblage, etc.).

Références

[1]

C. Pomerance   J. W. Smith. Reduction of huge, sparse matrices over a finite field via created catastrophes. Experimental Math. 1 (1992), 90-94, 1992.

[2]

D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithm, third Edition. Addison-Wesley, 1997.

[3]

C. Pomerance. A tale of two sieves. The Notices of the Amer. Math. Soc. 43 (1996), 1473-1485, 1996.

Ce document a été traduit de L^AT_EX par H^EV^EA