Nombre premier probable

En arithmétique modulaire, un nombre premier probable est un entier naturel qui satisfait à une condition (nécessaire mais pas suffisante) qui est satisfaite aussi par tous les nombres premiers. Les nombres premiers probables qui se révèlent finalement non premiers (c'est-à-dire composés) sont appelés pseudo-premiers. Il en existe une infinité, mais ils restent cependant rares pour chaque condition utilisée. Le test de Fermat pour la composition, qui est basé sur le petit théorème de Fermat énonce ce qui suit : soit un entier naturel n > 1, choisissons un certain entier naturel a premier avec n et calculons an − 1 modulo n. Si le résultat est différent de 1, n est composé. S'il est égal à 1, n est premier ou pas ; n est alors appelé un nombre « premier probable faible de base a ». Le test de Fermat peut être amélioré par l'usage du fait que les seules racines carrées de 1 modulo un nombre premier sont 1 et −1. Les nombres indiqués comme premiers par ce test renforcé sont connus comme des nombres « premiers probables forts de base a ». Un « nombre premier d'Euler probable » est un entier qui est indiqué premier par le théorème quelque peu renforcé qui affirme que pour n'importe quel nombre premier p, et n'importe quel a, a(p − 1)/2 = modulo p, où est le symbole de Legendre. Ce test est également efficace et il est au moins deux fois plus fort que le test de Fermat. Un nombre premier probable d'Euler qui est composé est appelé un nombre pseudo-premier d'Euler-Jacobi. La primalité probable est une base pour les algorithmes de test d'efficience de primalité, qui trouvent une application en cryptologie. Ces algorithmes sont généralement probabilistes de nature. L'idée est qu'alors il existe des bases composées a probablement premières pour n'importe quel a fixé, nous pouvons renverser les rôles : pour n'importe quel n composé fixé et un a choisi aléatoirement, nous pouvons espérer que n n'est pas une base a pseudo-première, avec une haute probabilité.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (4)

Séances de cours associées (1)

Integers: Bien commander et induction

Explore bien l'ordre, l'induction, la division euclidienne, et la factorisation primaire en entiers.

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é.

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.