Aller au contenu principal

Deux exemples : factorisation et PGCD

Les ordinateurs classiques qui existent aujourd'hui sont incroyablement rapides, et leur vitesse semble en constante augmentation. Pour cette raison, certains pourraient être tentés de croire que les ordinateurs sont si rapides qu'aucun problème computationnel n'est hors de leur portée.

Cette croyance est fausse. Certains problèmes computationnels sont si intrinsèquement complexes que, bien qu'il existe des algorithmes pour les résoudre, aucun ordinateur sur la planète Terre aujourd'hui n'est assez rapide pour exécuter ces algorithmes jusqu'à leur terme sur des entrées même de taille modeste dans la durée d'une vie humaine — voire dans la durée de vie de la Terre elle-même.

Pour expliquer cela davantage, introduisons le problème de factorisation des entiers.

Factorisation des entiers

Entrée : un entier N≥2N\geq 2
Sortie : la décomposition en facteurs premiers de NN

Par décomposition en facteurs premiers de NN, on entend une liste des facteurs premiers de NN et des exposants auxquels ils doivent être élevés pour obtenir NN par multiplication. Par exemple, les facteurs premiers de 1212 sont 22 et 3,3, et pour obtenir 1212 on doit prendre le produit de 22 à la puissance 22 et 33 à la puissance 1.1.

12=22⋅312 = 2^2 \cdot 3

À l'ordre des facteurs premiers près, il n'existe qu'une seule décomposition en facteurs premiers pour chaque entier positif N≥2,N\geq 2, ce qui est un fait connu sous le nom de théorème fondamental de l'arithmétique.

Quelques démonstrations de code simples en Python seront utiles pour mieux expliquer la factorisation des entiers et d'autres concepts liés à cette discussion. Les imports suivants sont nécessaires pour ces démonstrations.

# Added by doQumentation — required packages for this notebook
!pip install -q sympy
import math
from sympy.ntheory import factorint

La fonction factorint du package de mathématiques symboliques SymPy pour Python résout le problème de factorisation des entiers pour n'importe quelle entrée NN qu'on choisit. Par exemple, on peut obtenir la décomposition en facteurs premiers de 12, qui concorde naturellement avec la factorisation ci-dessus.

N = 12
print(factorint(N))
{2: 2, 3: 1}

Factoriser de petits nombres comme 1212 est facile, mais lorsque le nombre NN à factoriser devient plus grand, le problème devient plus difficile. Par exemple, exécuter factorint sur un nombre nettement plus grand provoque un court délai mais perceptible sur un ordinateur personnel typique.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))
{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

Pour des valeurs encore plus grandes de N,N, les choses deviennent impossiblement difficiles, du moins à ce qu'on sache. Par exemple, le RSA Factoring Challenge, qui a été organisé par RSA Laboratories de 1991 à 2007, offrait un prix en espèces de 100 000 $ pour factoriser le nombre suivant, qui comporte 309 chiffres décimaux (ou 1024 bits en écriture binaire). Le prix pour ce nombre n'a jamais été décroché et ses facteurs premiers restent inconnus.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Inutile de s'embêter à exécuter factorint sur RSA1024, il ne terminerait pas de notre vivant.

L'algorithme le plus rapide connu pour factoriser de grands entiers est le crible algébrique de corps de nombres. À titre d'exemple de son utilisation, le nombre du défi RSA RSA250, qui comporte 250 chiffres décimaux (ou 829 bits en écriture binaire), a été factorisé à l'aide du crible algébrique de corps de nombres en 2020. Le calcul a nécessité des milliers d'années-cœur CPU, réparties sur des dizaines de milliers de machines à travers le monde. Ici, on peut apprécier cet effort en vérifiant la solution.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)
True

La sécurité du cryptosystème à clé publique RSA repose sur la difficulté computationnelle de la factorisation des entiers, dans le sens où un algorithme efficace pour la factorisation des entiers le briserait.

Considérons ensuite un problème connexe mais très différent, qui est le calcul du plus grand commun diviseur (ou PGCD) de deux entiers.

Plus grand commun diviseur (PGCD)

Entrée : des entiers non négatifs NN et M,M, dont au moins l'un est positif
Sortie : le plus grand commun diviseur de NN et MM

Le plus grand commun diviseur de deux nombres est le plus grand entier qui divise exactement les deux.

Ce problème est facile à résoudre avec un ordinateur — il a à peu près le même coût computationnel que multiplier les deux nombres d'entrée ensemble. La fonction gcd du module math de Python calcule le plus grand commun diviseur de nombres considérablement plus grands que RSA1024 en un clin d'œil. (En fait, RSA1024 est le PGCD des deux nombres dans cet exemple.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

C'est possible parce que nous disposons d'algorithmes très efficaces pour calculer les PGCD, dont le plus connu est l'algorithme d'Euclide, découvert il y a plus de 2 000 ans.

Pourrait-il exister un algorithme rapide pour la factorisation des entiers que nous n'avons pas encore découvert, permettant de factoriser des grands nombres comme RSA1024 en un clin d'œil ? La réponse est oui. Bien qu'on pourrait s'attendre à ce qu'un algorithme efficace pour la factorisation, aussi simple et élégant que l'algorithme d'Euclide pour le calcul des PGCD, aurait déjà été découvert, rien n'exclut l'existence d'un algorithme classique très rapide pour la factorisation des entiers, au-delà du fait que nous n'en avons pas trouvé jusqu'à présent. On pourrait en découvrir un demain — mais ne retiens pas ton souffle. Des générations de mathématiciens et d'informaticiens ont cherché, et factoriser des nombres comme RSA1024 reste hors de notre portée.