Décomposition en produit de facteurs premiers - Définition

Applications pratiques

Soient deux grands nombres premiers donnés, il est facile d'en obtenir le produit. Par contre, il est beaucoup plus difficile de trouver les facteurs premiers de celui-ci. C'est ce que l'on appelle une fonction trappe. Ceci s'applique pour les systèmes modernes en cryptologie. Si une méthode rapide était trouvée pour résoudre le problème de la factorisation des nombres entiers, alors plusieurs systèmes cryptologiques importants seraient cassés, incluant l'algorithme à clé publique RSA et le générateur de nombres pseudo-aléatoires Blum Blum Shub. La mise au point d'un ordinateur quantique est une de ces méthodes.

Bien que la factorisation soit une manière de casser ces systèmes, il peut exister d'autres manières de les casser qui n'impliquent pas la factorisation. Ainsi, il est possible que le problème de la factorisation entière soit vraiment difficile, mais ces systèmes peuvent quand même être cassés rapidement. Une exception rare est le générateur Blum Blum Shub. Il a été prouvé qu'il est exactement aussi difficile que la décomposition en produit de facteurs premiers : si vous pouvez casser le générateur en temps polynomial alors, vous pouvez factoriser les entiers en temps polynomial, et vice versa.

Algorithmes de factorisation

But spécial

Les temps d'exécution des algorithmes de factorisation à but spécial dépend des propriétés de ses facteurs inconnus : taille, forme spéciale, etc. De manière exacte, le temps d'exécution dépend de ce qui varie entre les algorithmes.

• Essais de divisions
• Algorithme rho de Pollard
• Algorithme p-1 de Pollard
• Factorisation en courbe elliptique de Lenstra
• Congruence de carrés (Méthode de factorisation de Fermat)
• Crible spécial de corps de nombres (SNFS)

But général

Le temps d'exécution des algorithmes de factorisation à but général dépend seulement de la taille de l'entier à factoriser. Ceci est le type d'algorithme utilisé pour factoriser les nombres RSA. La plupart des algorithmes de factorisation à but général sont basés sur la méthode des congruence de carrés.

• Crible quadratique
• Crible général de corps de nombres (GNFS)