TERMIUM Plus^®

Fiche 1,  Justifications,  Anglais

Record number: 1, Textual support number: 1 CONT

I shall describe here two public-key cryptosystems based on NP problems (i.e. nondeterministic, polynomial time problems,): the trapdoor knapsack system, developed by Merkle and me (i.e. Martin E. Hellman), and the RSA system, developed by Ronald Rivest, Adi Shamir and Leonard Adleman at the Massachusetts Institute of Technology. The first of these cryptosystems is based on a well-known NP problem called the knapsack or subset sum problem [...]  1, fiche 1, Anglais, - trapdoor%20knapsack%20system

Fiche 1,  Justifications,  Français

Record number: 1, Textual support number: 1 CONT

Nous décrirons ici deux cryptosystèmes à clef révélée fondés sur les problèmes NP(c'est-à-dire non résolubles en temps polynomial) : le système à empilement mis au point par Ralph Merkle et moi-même, et le système RSA, dû aux travaux de Ronald Rivest, Adi Shamir et Leonard Adleman à l'Institut de technologie du Massachusetts. Le premier de ces cryptosystèmes est fondé sur un problème NP bien connu, concernant la recherche de sous-ensembles de somme donnée d’un ensemble de nombres [...]  1, fiche 1, Français, - syst%C3%A8me%20%C3%A0%20empilement

Fiche 1,  Justifications,  Espagnol

Fiche 2,  Justifications,  Anglais

Record number: 2, Textual support number: 1 DEF

An NP, [i.e. nondeterministic, polynomial time], problem from which a trapdoor one-way function can be derived.  1, fiche 2, Anglais, - knapsack%20problem

Fiche 2,  Justifications,  Français

Record number: 2, Textual support number: 1 DEF

Un problème NP [c'est-à-dire non résoluble en temps polynomial, ] à partir duquel on peut construire une fonction à sens unique et à gâche.  1, fiche 2, Français, - probl%C3%A8me%20d%26rsquo%3Bempilement

Fiche 2,  Justifications,  Espagnol

Fiche 3,  Justifications,  Anglais

Fiche 3,  Justifications,  Français

Record number: 3, Textual support number: 1 DEF

Problème difficile dont la résolution est possible par un algorithme non-déterministe de complexité polynomiale ou par un algorithme déterministe de complexité exponentielle.  1, fiche 3, Français, - probl%C3%A8me%20de%20co%C3%BBt%20NP

Fiche 3,  Justifications,  Espagnol

Fiche 4,  Justifications,  Anglais

Fiche 4,  Justifications,  Français

Record number: 4, Textual support number: 1 DEF

Problème de coût NP tel que s’il admet un algorithme déterministe polynomial alors tout problème de coût NP en admettra un.  1, fiche 4, Français, - probl%C3%A8me%20NP%2Dcomplet

Fiche 4,  Justifications,  Espagnol

Fiche 5,  Justifications,  Anglais

Record number: 5, Textual support number: 1 OBS

Multinomial : same as polynomial.  3, fiche 5, Anglais, - complete%20multinomial

Record number: 5, Textual support number: 1 CONT

A complete multinomial of degree n in m variables is the sum of all homogeneous multinomials from zero degree through the nth degree.  1, fiche 5, Anglais, - complete%20multinomial

Fiche 5,  Justifications,  Français

Record number: 5, Textual support number: 1 OBS

Voir problème NP complet.  1, fiche 5, Français, - polyn%C3%B4me%20complet

Fiche 5,  Justifications,  Espagnol

Fiche 6,  Justifications,  Anglais

Record number: 6, Textual support number: 1 CONT

Problems in the class NP (which stands for nondeterministic, polynomial time) are characterized by the fact that although it is easy to check a nondeterministic, or guessed, solution, it is hard to find a correct solution: As the size n of an NP problem increases, the number of computational steps and hence the time required to check a solution increase in proportion to a polynomial function of n such as [the square of n] (...), but all known methods of finding a solution increase in proportion to a more rapidly growing function of n, typically an exponential one (...)  1, fiche 6, Anglais, - NP%20problem

Fiche 6,  Justifications,  Français

Record number: 6, Textual support number: 1 CONT

Les problèmes de classe NP(c'est-à-dire non résolubles en temps polynomial) ont la propriété fondamentale suivante : bien qu'il soit facile de vérifier si une valeur donnée est solution, il est très difficile de les résoudre sans information complémentaire. Quand la «taille» n d’un problème NP augmente, le nombre d’étapes de calcul, et donc le temps requis pour vérifier une solution, croît comme une fonction polynomiale de n, telle [le carré de n](...) ;toutes les méthodes connues pour trouver une solution exigent un temps de calcul croissant en fonction de n, beaucoup plus rapidement que toute fonction polynôme; ce temps de calcul croît généralement comme une fonction exponentielle(...)  1, fiche 6, Français, - probl%C3%A8me%20NP

Fiche 6,  Justifications,  Espagnol