Séance de cours

Modular Arithmetic : Optimisation de l'exponentiation

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.

Description

Cette séance de cours se concentre sur l'optimisation des calculs d'exponentiation en arithmétique modulaire, en soulignant l'importance de rester dans un domaine fixe pour assurer des opérations efficaces. L'instructeur explique la technique de réduction de la complexité temporelle de l'exponentiation par l'arithmétique modulaire, illustrant comment elle peut être appliquée pour déterminer si un nombre est premier. La séance de cours se penche sur la nature récursive des calculs, détaillant le processus de calcul efficace des puissances en décomposant des multiplications complexes. En utilisant des opérations modulaires, l'orateur montre comment minimiser le nombre d'opérations nécessaires, ce qui permet de gagner beaucoup de temps dans les tâches de calcul.

Source officielle

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.

Nombre premier

vignette|Nombres naturels de zéro à cent. Les nombres premiers sont marqués en rouge. vignette|Le nombre 7 est premier car il admet exactement deux diviseurs positifs distincts. Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs. Ces deux diviseurs sont 1 et le nombre considéré, puisque tout nombre a pour diviseurs 1 et lui-même (comme le montre l’égalité n = 1 × n), les nombres premiers étant ceux qui ne possèdent pas d'autre diviseur.

Classe de complexité

En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.

P (complexité)

La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques. Par définition, un problème de décision est dans P s'il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème est décidé en temps polynomial. Les problèmes dans P sont considérés comme « faisables » (feasible en anglais), faciles à résoudre (dans le sens où on peut le faire relativement rapidement).

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.

Afficher plus

Séances de cours associées (64)

Exposentiation: Complexité temporelle

Couvre l'algorithme d'exponentiation rapide et sa complexité temporelle, les propriétés des nombres premiers et le schéma de cryptage El-Gamal.

Nombres premiers et algorithmes

Couvre les nombres premiers, les algorithmes de test de primalité, l'arithmétique modulaire et les méthodes d'exponentiation efficaces.

Tests de nombres premiers et de primalité

Couvre les nombres premiers, la cryptographie RSA et les tests de primalité, y compris le théorème des restes chinois et le test de Miller-Rabin.

Théorie des nombres: exemples d'exponentiation modulaire

Couvre des exemples d'exponentiation modulaire, de complexités, de théorème de Lame, de conjecture de Collatz et de nombres premiers.

Théorie des nombres: Division, Reste, Congruence

Couvre la théorie des nombres, la division, le reste, la congruence, les nombres premiers, la représentation entière et l'algorithme euclidien.

Afficher plus

Concepts associés (32)

Computational complexity

Afficher plus