FACTORISATION

ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 831 mots
  •  • 3 médias

Dans le chapitre « Tests de primalité et de factorisation »  : […] Un entier m composite (non premier) possède nécessairement un facteur plus petit que m . Il en résulte que l'essai successif des divisions exactes de m par les nombres 2, 3, 4..., [ m ] constitue à la fois un algorithme de factorisation – qui détermine les diviseurs de m si m est composite – et un test de primalité – si aucun diviseur n'a été o […] Lire la suite☛ http://www.universalis.fr/encyclopedie/algorithmique/#i_93537

COMPLEXITÉ, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 627 mots

Dans le chapitre « Les classes P et NP »  : […] Ce domaine a ouvert la voie dans la décennie 1970 à une analyse d'un niveau plus fin, appelée théorie des classes de complexité, où l'on se pose des questions du type suivant : peut-on décomposer en facteurs premiers un nombre de n chiffres en utilisant un temps de calcul t majoré par un polynôme en n (on parle de temps polynomial) ? Les pro […] Lire la suite☛ http://www.universalis.fr/encyclopedie/complexite-mathematique/#i_93537

CRYPTOLOGIE

  • Écrit par 
  • Jacques STERN
  •  • 5 754 mots
  •  • 2 médias

Dans le chapitre « Les mécanismes mis en œuvre »  : […] La quasi-totalité des systèmes cryptographiques asymétriques repose sur l'emploi de méthodes mathématiques issues de la théorie des nombres et développées au xix e  siècle, notamment dans les travaux de l'Allemand Carl Friedrich Gauss. Pour les appréhender, on doit substituer à l'arithmétique ordinaire des mécanismes de calcul modulo  n où les nom […] Lire la suite☛ http://www.universalis.fr/encyclopedie/cryptologie/#i_93537