Séance de cours

Problème de registre discret : la méthode Rho de Pollard

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

MATH-489: Number theory II.d - Cryptography

. ...

Description

Cette séance de cours couvre le problème de log discret et introduit la méthode rho de Pollard, qui vise à trouver des collisions dans un groupe cyclique d'ordre N généré par g. La méthode consiste à cloisonner le groupe, à fixer les valeurs initiales et à calculer des solutions itératives. En adaptant l'idée de Pollard, la séance de cours explore la façon de factoriser les entiers et de trouver des collisions efficacement, en mettant l'accent sur l'utilisation constante de la mémoire et le calcul récursif.

Enseignant·e

Dimitar Petkov Jetchev

Source officielle

Concepts associés (32)

Décomposition en produit de facteurs premiers

vignette|Décomposition du nombre 864 en facteurs premiers En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers ou encore plus couramment la décomposition en facteurs premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers. Par exemple, si le nombre donné est 45, la factorisation en nombres premiers est 3 × 5, soit 3 × 3 × 5.

Entier quadratique

En mathématiques, un entier quadratique est un nombre complexe, racine d'un polynôme unitaire du second degré à coefficients entiers. La notion de nombre algébrique de degré inférieur ou égal à 2 est plus générale : elle correspond à un nombre complexe, racine d'un polynôme du second degré à coefficients seulement rationnels. Ces nombres particuliers disposent de propriétés algébriques.

Entier algébrique

En mathématiques, un entier algébrique est un élément d'un corps de nombres qui y joue un rôle analogue à celui d'un entier relatif dans le corps des nombres rationnels. L'étude des entiers algébriques est à la base de l'arithmétique des corps de nombres, et de la généralisation dans ces corps de notions comme celles de nombre premier ou de division euclidienne. Par définition, un entier algébrique est une racine d'un polynôme unitaire à coefficients dans Z.

Entier d'Eisenstein

thumb|Les entiers d'Eisenstein sont les points d'intersection d'un treillis triangulaire dans le plan complexe. En mathématiques, les 'entiers d'Eisenstein', nommés en l'honneur du mathématicien Gotthold Eisenstein, sont les nombres complexes de la forme où a et b sont des entiers relatifs et est une racine cubique primitive de l'unité (souvent autrement notée j). Les entiers d'Eisenstein forment un réseau triangulaire dans le plan complexe. Ils contrastent avec les entiers de Gauss qui forment un réseau carré dans le plan complexe.

Theory of computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

Afficher plus

Séances de cours associées (64)

Complexité et induction: Algorithmes et preuves

Couvre la complexité, les algorithmes et les preuves du pire cas, y compris l'induction mathématique et la récursion.

Propriétés de base MOOC: Analyse I MOOC: Analyse I (partie 1) : Prélude, notions de base, les nombres réels

Couvre les propriétés de base des nombres naturels, y compris les relations d'ordre et les inverses.

L'algorithme de Shor : les entiers de factoring

Couvre les bases de l'algorithme de Shor pour factoriser les entiers et les étapes impliquées dans l'algorithme quantique.

Fonctions et entiers

Couvre les fonctions, les entiers, le GCD et le raisonnement par récurrence, y compris l'algorithme euclidien et le principe d'induction.

Entiers et Anneaux

Couvre les entiers, les anneaux, les sous-anneaux, l'inversibilité, les diviseurs de zéro et les relations d'équivalence dans les fractions formelles.

Afficher plus

Concepts associés (32)

Décomposition en produit de facteurs premiers

Entier quadratique

Entier algébrique

Entier d'Eisenstein

Theory of computation

Afficher plus