FACTORISATION

Articles

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD, Philippe FLAJOLET
  • 6 652 mots
  • 3 médias
  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 √ n logn), ce qui représente une amélioration substantielle par rapport à l'algorithme simple...

• COMPLEXITÉ, mathématique

  • Écrit par Jean-Paul DELAHAYE
  • 1 626 mots
  ...et b en temps polynomial. Plus généralement, les 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...

• CRYPTOLOGIE

  • Écrit par Jacques STERN
  • 5 770 mots
  • 3 médias
  ...inverse qui permet le déchiffrement est aussi une exponentiation, 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...