FACTORISATION

Ce sujet est traité dans les articles suivants :

1.  ALGORITHMIQUE

Écrit par : Philippe COLLARD, Philippe FLAJOLET

Dans le chapitre "Tests de primalité et de factorisation"  : … d'entiers comportant plusieurs milliers de chiffres décimaux. Par contraste, le problème de la *factorisation d'entiers est algorithmiquement beaucoup plus difficile. Les meilleurs algorithmes connus présentent une complexité de l'ordre de exp(c …]… Lire la suite

2.  COMPLEXITÉ, mathématique

Écrit par : Jean-Paul DELAHAYE

Dans le chapitre "Les classes P et NP"  : … problèmes dont on peut ainsi vérifier les solutions en temps polynomial constituent la classe NP. *Le problème de la factorisation est dans la classe NP (d'après ce que nous venons de dire concernant la multiplication des entiers), en revanche on ignore si le problème de la factorisation est dans la classe P, et l'on pense généralement qu'il n'y… Lire la suite

3.  CRYPTOLOGIE

Écrit par : Jacques STERN

Dans le chapitre "Les mécanismes mis en œuvre"  : … mais le calcul de l'exposant correspondant, gardé secret, nécessite la connaissance de la *factorisation de n. On rappelle qu'un nombre premier n'admet d'autre diviseur que 1 et lui-même ; la suite des nombres premiers est infinie et commence par 2, 3, 5, 7, etc. Tout nombre s'écrit comme produit de nombres premiers ; ainsi 35… Lire la suite