Fonction de hachageQuand il s'agit de mettre dans un tableau de taille raisonnable (typiquement résidant dans la mémoire principale de l'ordinateur) un ensemble de données de taille variable et arbitraire, on utilise une fonction de hachage pour attribuer à ces données des indices de ce tableau. Par conséquent, une fonction de hachage est une fonction qui associe des valeurs de taille fixe à des données de taille quelconque. Les valeurs renvoyées par une fonction de hachage sont appelées valeurs de hachage, codes de hachage, résumés, signatures ou simplement hachages.
Fonction de hachage parfaitdroite|vignette|240x240px| Une fonction de hachage parfait pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. droite|vignette|240x240px| Une fonction de hachage parfait minimal pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. En informatique, une fonction de hachage parfait h pour un ensemble S est une fonction de hachage qui associe des éléments distincts de S à un ensemble de m entiers, sans collisions. En termes mathématiques, c'est une fonction injective.
Hachage universelEn mathématiques et en informatique, le hachage universel, en anglais universal hashing, (dans un algorithme probabiliste ou un bloc de données) est une méthode qui consiste à sélectionner aléatoirement une fonction de hachage dans une famille de fonctions de hachages qui ont certaines propriétés mathématiques. Cela permet de minimiser la probabilité de collision de hachage. Plusieurs familles de fonctions de hachages sont connues (pour hacher des entiers, des chaînes de caractères ou des vecteurs), et leur calcul est souvent très efficace.
Table de hachageUne table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif. Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie.
Fonction de hachage cryptographiqueUne fonction de hachage cryptographique est une fonction de hachage qui, à une donnée de taille arbitraire, associe une image de taille fixe, et dont une propriété essentielle est qu'elle est pratiquement impossible à inverser, c'est-à-dire que si l'image d'une donnée par la fonction se calcule très efficacement, le calcul inverse d'une donnée d'entrée ayant pour image une certaine valeur se révèle impossible sur le plan pratique. Pour cette raison, on dit d'une telle fonction qu'elle est à sens unique.
Dynamic perfect hashingIn computer science, dynamic perfect hashing is a programming technique for resolving collisions in a hash table data structure. While more memory-intensive than its hash table counterparts, this technique is useful for situations where fast queries, insertions, and deletions must be made on a large set of elements. static hashing#FKS Hashing The problem of optimal static hashing was first solved in general by Fredman, Komlós and Szemerédi.
Locality sensitive hashingLocality sensitive hashing (LSH) est une méthode de recherche approximative dans des espaces de grande dimension. C'est une solution au problème de la malédiction de la dimension qui apparait lors d'une recherche des plus proches voisins en grande dimension. L'idée principale est d'utiliser une famille de fonction de hachage choisies telles que des points proches dans l'espace d'origine aient une forte probabilité d'avoir la même valeur de hachage. La méthode a de nombreuses applications en vision artificielle, traitement automatique de la langue, bio-informatique.
Cuckoo hashingCuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches in a variation of the behavior referred to as brood parasitism; analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location in the table.
Mise en gageEn cryptologie, la mise en gage () est un processus qui permet à une personne de « mettre en gage » une valeur (ou un énoncé) tout en la maintenant cachée aux autres, avec la possibilité de révéler cette valeur plus tard en prouvant que c'est bien la valeur qui avait été mise en gage. La mise en gage est conçue de telle sorte que la personne est liée à la valeur mise en gage. En pratique, la mise en gage se fait en calculant une valeur de mise en gage à partir de la valeur que l'on veut cacher et en communiquant cette valeur de mise en gage à un destinataire.
Espace de FréchetUn espace de Fréchet est une structure mathématique d'espace vectoriel topologique satisfaisant certains théorèmes relatifs aux espaces de Banach même en l'absence d'une norme. Cette dénomination fait référence à Maurice Fréchet, mathématicien français ayant participé notamment à la fondation de la topologie et à ses applications en analyse fonctionnelle. C'est dans ce dernier domaine que la structure des espaces de Fréchet se révèle particulièrement utile, notamment en fournissant une topologie naturelle aux espaces de fonctions infiniment dérivables et aux espaces de distributions.
Table de hachage distribuéeUne table de hachage distribuée (ou DHT pour Distributed Hash Table), est une technique permettant la mise en place d’une table de hachage dans un système réparti. Une table de hachage est une structure de données de type clé → valeur. Chaque donnée est associée à une clé et est distribuée sur le réseau. Les tables de hachage permettent de répartir le stockage de données sur l’ensemble des nœuds du réseau, chaque nœud étant responsable d’une partie des données.
Cryptographiethumb|La machine de Lorenz utilisée par les nazis durant la Seconde Guerre mondiale pour chiffrer les communications militaires de haut niveau entre Berlin et les quartiers-généraux des différentes armées. La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés. Elle se distingue de la stéganographie qui fait passer inaperçu un message dans un autre message alors que la cryptographie rend un message supposément inintelligible à autre que qui de droit.
Hachage cohérentLe hachage cohérent est un type particulier de hachage. Lorsque la table de hachage change de taille et que le hachage cohérent est employé, seulement clés ont besoin d’être redistribuées en moyenne, où est le nombre de clés et est le nombre d'éléments dans la table de hachage. En comparaison, dans une table de hachage classique, un changement dans le nombre d'éléments de la table a pour conséquence la réorganisation de l'ensemble ou presque des clés. À l'origine conçue par Karger et coll.
Mot de passethumb|Formulaire de connexion de Wikipédia en anglais, nécessitant un mot de passe. Un mot de passe est un mot ou une série de caractères utilisés comme moyen d'authentification pour prouver son identité lorsque l'on désire accéder à un lieu protégé, à un compte informatique, un ordinateur, un logiciel ou à un service dont l'accès est limité et protégé. Le mot de passe doit être tenu secret pour éviter qu'un tiers non autorisé puisse accéder à la ressource ou au service.
Schéma (géométrie algébrique)En mathématiques, les schémas sont les objets de base de la géométrie algébrique, généralisant la notion de variété algébrique de plusieurs façons, telles que la prise en compte des multiplicités, l'unicité des points génériques et le fait d'autoriser des équations à coefficients dans un anneau commutatif quelconque.
Chosen-ciphertext attackA chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidden secret key used for decryption. For formal definitions of security against chosen-ciphertext attacks, see for example: Michael Luby and Mihir Bellare et al. A number of otherwise secure schemes can be defeated under chosen-ciphertext attack.
Fonction à sens uniquevignette|Panneau de signalisation routière de sens unique Une fonction à sens unique (ou one-way function en anglais) est une fonction qui peut être aisément calculée, mais qui est difficile à inverser — c'est-à-dire qu'étant donnée une , il est difficile de lui trouver un antécédent. Les fonctions à sens unique sont utilisées en cryptographie asymétrique et dans les fonctions de hachage cryptographiques. La théorie de la complexité des algorithmes est un élément central de la notion de fonction à sens unique.
Générateur de nombres aléatoiresUn générateur de nombres aléatoires, random number generator (RNG) en anglais, est un dispositif capable de produire une suite de nombres pour lesquels il n'existe aucun lien calculable entre un nombre et ses prédécesseurs, de façon que cette séquence puisse être appelée « suite de nombres aléatoires ». Par extension, on utilise ce terme pour désigner des générateurs de nombres pseudo aléatoires, pour lesquels ce lien calculable existe, mais ne peut pas « facilement » être déduit.
F-spaceIn functional analysis, an F-space is a vector space over the real or complex numbers together with a metric such that Scalar multiplication in is continuous with respect to and the standard metric on or Addition in is continuous with respect to The metric is translation-invariant; that is, for all The metric space is complete. The operation is called an F-norm, although in general an F-norm is not required to be homogeneous. By translation-invariance, the metric is recoverable from the F-norm.
Borne supérieure et borne inférieureEn mathématiques, les notions de borne supérieure et borne inférieure d'un ensemble de nombres réels interviennent en analyse, comme cas particulier de la définition générale suivante : la borne supérieure (ou le supremum) d'une partie d'un ensemble (partiellement) ordonné est le plus petit de ses majorants. Une telle borne n'existe pas toujours, mais si elle existe alors elle est unique. Elle n'appartient pas nécessairement à la partie considérée. Dualement, la borne inférieure (ou l'infimum) d'une partie est le plus grand de ses minorants.
