Séance de cours

Nombres premiers et algorithmes

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 explore le concept de nombres premiers et les algorithmes utilisés pour déterminer si un grand nombre est premier. L'instructeur discute de l'importance de s'arrêter à la racine carrée d'un nombre lors du test de primalité, ainsi que de la complexité des différents algorithmes. La séance de cours se penche sur l'arithmétique modulaire, démontrant comment elle peut simplifier les calculs, en particulier dans l'exponentiation. En décomposant les exposants sous forme binaire, on peut calculer efficacement de grandes exponentiations. L'instructeur introduit également des algorithmes probabilistes, qui fournissent la plupart du temps des réponses correctes en utilisant la randomisation. La séance de cours se termine par une discussion sur la complexité informatique de l'exponentiation et l'importance d'algorithmes efficaces dans le contexte de la recherche sur les nombres premiers.

Source officielle

Proximité ontologique

Mathématiques

Théorie des nombres: Théorie des nombres

Concepts associés (30)

Test de primalité

vignette|Le 39e nombre premier de Mersenne découvert à ce jour pour un article sur la primalité Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Le test le plus simple est celui des divisions successives : pour tester N, on vérifie s’il est divisible par l’un des entiers compris au sens large entre 2 et N-1. Si la réponse est négative, alors N est premier, sinon il est composé.

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.

Test de primalité AKS

Le test de primalité AKS (aussi connu comme le test de primalité Agrawal-Kayal-Saxena et le test cyclotomique AKS) est un algorithme de preuve de primalité déterministe et généraliste (fonctionne pour tous les nombres) publié le par trois scientifiques indiens nommés Manindra Agrawal, Neeraj Kayal et Nitin Saxena (A.K.S). Ce test est le premier en mesure de déterminer la primalité d'un nombre dans un temps polynomial. Ce test a été publié dans un article scientifique intitulé « PRIMES is in P ».

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.

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.

Afficher plus

Séances de cours associées (64)

Modular Arithmetic : Optimisation de l'exponentiation

Explore l'optimisation de l'exponentiation en arithmétique modulaire pour des calculs efficaces et la détermination des nombres premiers.

Le petit théorème de Fermat

Explore le Petit Théorème de Fermat, ses extensions, ses algorithmes de test de primalité, et la signification des nombres premiers dans la cryptographie.

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.

Nombres principaux : Approches déterministes

Introduit des approches déterministes pour identifier les nombres premiers et couvre les algorithmes et l'arithmétique modulaire pour les essais de nombres premiers.

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.

Afficher plus

Concepts associés (30)

Test de primalité

Nombre premier

Test de primalité AKS

Computational complexity

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

Afficher plus