Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

ALL Algorithme

Dans cours

MATH-489: Number theory II.d - Cryptography

. ...

Description

Cette séance de cours couvre l'algorithme LLL, qui est utilisé pour la réduction du réseau. Il explique le concept de points symétriques centraux, la condition de Lovasz, l'intuition derrière le changement de base, et l'orthogonalité. L'instructeur discute de la constante d'Hermite, du théorème de Minkowski et du discriminant dans le contexte des treillis de plein rang.

Enseignant·e

Dimitar Petkov Jetchev

Source officielle

Concepts associés (23)

Ideal lattice

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient.

Problème de réseau

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes.

Réseau (géométrie)

En mathématiques, un réseau d'un espace (vectoriel) euclidien est un sous-groupe discret de l’espace, de rang fini n. Par exemple, les vecteurs de Rn à coordonnées entières dans une base forment un réseau de Rn. Cette notion permet de décrire mathématiquement des maillages, comme celui correspondant à la figure 1. thumb|Fig. 1. Un réseau est un ensemble discret disposé dans un espace vectoriel réel de dimension finie de manière régulière, au sens où la différence de deux éléments du réseau est encore élément du réseau.

Suite de polynômes orthogonaux

En mathématiques, une suite de polynômes orthogonaux est une suite infinie de polynômes p0(x), p1(x), p2(x) ... à coefficients réels, dans laquelle chaque pn(x) est de degré n, et telle que les polynômes de la suite sont orthogonaux deux à deux pour un produit scalaire de fonctions donné. Cette notion est utilisée par exemple en cryptologie ou en analyse numérique. Elle permet de résoudre de nombreux problèmes de physique, comme en mécanique des fluides ou en traitement du signal.

Lattice-based cryptography

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers.

Afficher plus

Séances de cours associées (37)

Bases et polynômes orthogonaux/orthonormaux

Explore les bases orthogonales et orthonormées, le processus de Gram-Schmidt et les polynômes orthogonaux en physique.

Éléments distincts : fonctions de comptage et de hachage

Couvre le comptage d'éléments distincts à l'aide de fonctions de hachage et de l'astuce médiane.

Sans titre

Apprentissage latent de l'arbre

Explore l'apprentissage de l'arbre latent, couvrant les propriétés des nœuds, les relations fraternelles et la structure algorithmique.

Algorithme de Stein : Test d'identité polynomiale

Explore l'algorithme Stein pour le test d'identité polynomiale et la minimisation d'un problème de coupe.

Afficher plus

Concepts associés (23)

Ideal lattice

Problème de réseau

Réseau (géométrie)

Suite de polynômes orthogonaux

Lattice-based cryptography

Afficher plus