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

Factorisation des polynômes : complexité et algorithmes

Dans cours

MATH-489: Number theory II.d - Cryptography

. ...

Description

Cette séance de cours couvre la complexité de l'affacturage des polynômes, en mettant l'accent sur les défis et les algorithmes impliqués. L'instructeur discute des subtilités du calcul des facteurs non triviaux et des implications pour la sécurité dans la factorisation des entiers.

Enseignant·e

Dimitar Petkov Jetchev

Source officielle

Proximité ontologique

Mathématiques

Algèbre: Algèbre générale

Informatique théorique

Theory of computation: Théorie de la complexité (informatique théorique)

Concepts associés (32)

Complexité en temps

En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Polynomial greatest common divisor

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers. In the important case of univariate polynomials over a field the polynomial GCD may be computed, like for the integer GCD, by the Euclidean algorithm using long division. The polynomial GCD is defined only up to the multiplication by an invertible constant.

Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.

Algorithme probabiliste

En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].

Afficher plus

Séances de cours associées (36)

Factorisation entière : méthodes et algorithmes

Explore les méthodes et les algorithmes pour la factorisation entière, y compris les tests pour la fluidité B et le calcul des petits premiers.

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.

Factorisation entière: Sieve Quadratic

Couvre la méthode Quadratic Sieve pour la factorisation entière, soulignant l'importance de choisir les bons paramètres pour la factorisation efficace.

Théorie des nombres : GCD et LCM

Couvre GCD, LCM et l'algorithme euclidien pour un calcul efficace de GCD.

Algèbre élémentaire: ensembles numériques

Explore les concepts d'algèbre élémentaire liés aux ensembles numériques et aux nombres premiers, y compris la factorisation et les propriétés uniques.

Afficher plus

Concepts associés (32)

Complexité en temps

Computational complexity

Polynomial greatest common divisor

Théorie de la complexité (informatique théorique)

Algorithme probabiliste

Afficher plus