Factoriser

"factoriser" dans l'encyclopédie

• SHOR PETER (1959- )

  • Écrit par Bernard PIRE
  • 1 199 mots

  Il développe ensuite un algorithme quantique capable de factoriser des nombres entiers, prouesse hors d'atteinte des ordinateurs classiques, et résultat de première importance pour la cryptographie. Ses travaux sur les codes correcteurs ont également levé des obstacles à la réalisation des ordinateurs quantiques.

• COMPLEXITÉ, mathématique

  • Écrit par Jean-Paul DELAHAYE
  • 8 935 mots

  C'est une question importante pour la cryptographie, où casser certains algorithmes cryptographiques est équivalent à factoriser des entiers. Il semble intuitivement clair que la classe NP n'est pas identique à la classe P – car il est certainement plus facile de vérifier une solution proposée que de la rechercher ! Pourtant, la démonstration de l'affirmation P ≠ NP est l'une des énigmes les plus récalcitrantes de la théorie des classes de complexité.

• MÉSOPOTAMIE Les mathématiques

  • Écrit par Christine PROUST
  • 19 861 mots
  • 7 médias

  Le plus courant de ces algorithmes est celui qui permettait de factoriser des nombres pour calculer des inverses, des racines carrées ou des racines cubiques. Un autre exemple de mathématiques abstraites est fourni par la tablette Plimpton 322 qui donne une liste de triplets pythagoriciens. Cette tablette est connue largement au-delà du cercle des spécialistes, notamment chez les mathématiciens qui en ont fait leurs délices.

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD et Philippe FLAJOLET
  • 36 583 mots
  • 3 médias

  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 en O(2n/2), mais ne permet guère de factoriser des entiers de plus de cinquante chiffres décimaux. Codages arithmétiques à clefs publiques. La disproportion entre la complexité algorithmique de la factorisation et la complexité de la construction de nombres premiers est à l'origine d'un système de codage dû à Rivest, Shamir et Adleman (1979).

• PROGRAMMATION

  • Écrit par Jean-François MONIN
  • 42 295 mots

  Cela permet de factoriser une partie du code et constitue l'une des formes les plus simples de modularité – d'autres, plus évoluées, apparaîtront plus bas, avec les notions de types abstraits et de classes. Lorsque la procédure rend une valeur en fin d'exécution, on la nomme une fonction et au lieu d'être appelée en tant qu'instruction, elle est invoquée à l'intérieur d'une expression.