Logo
Unionpédia
Communication
Disponible sur Google Play
Nouveau! Téléchargez Unionpédia sur votre appareil Android™!
Gratuit
Accès plus rapide que le navigateur!
 

Test de primalité de Miller-Rabin

Indice Test de primalité de Miller-Rabin

En mathématiques, le test de primalité de Miller-Rabin est un test de primalité probabiliste, de type Monte Carlo: étant donné un nombre entier, il donne une réponse oui/non pour conclure soit de façon certaine que celui-ci est composé, soit qu'il est probablement premier.

47 relations: Algorithme déterministe, Algorithme probabiliste, Anneau ℤ/nℤ, Éditions Dunod, Belin éditeur, Chiffrement RSA, Comparaison asymptotique, Congruence sur les entiers, Corps (mathématiques), Corps fini, CRC Press, Cryptographie, Cryptographie asymétrique, Cryptosystème de ElGamal, Digital Signature Algorithm, Entier naturel, Exponentiation modulaire, Exponentiation rapide, Factorisation, Faux positif, Gary L. Miller, GNU MP, Hypothèse de Riemann généralisée, Indicatrice d'Euler, Logarithme discret, Louis Monier (programmeur), Mathématiques, Méthode de Monte-Carlo, Michael Rabin, MIT Press, National Institute of Standards and Technology, Nombre composé, Nombre de Carmichael, Nombre premier, Nombre pseudo-premier, P (complexité), Parité (arithmétique), Petit théorème de Fermat, Probabilité conditionnelle, Proposition contraposée, Racine carrée, Springer Science+Business Media, Test de primalité, Test de primalité AKS, Test de primalité de Fermat, Test de primalité de Solovay-Strassen, Théorème des nombres premiers.

Algorithme déterministe

En Informatique, un algorithme déterministe est un algorithme qui, étant donné une entrée particulière, produira toujours la même sortie, avec la machine sous-jacente passant toujours par la même séquence d'états.

Nouveau!!: Test de primalité de Miller-Rabin et Algorithme déterministe · Voir plus »

Algorithme probabiliste

En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard.

Nouveau!!: Test de primalité de Miller-Rabin et Algorithme probabiliste · Voir plus »

Anneau ℤ/nℤ

En mathématiques, et plus particulièrement en algèbre, (ℤ/nℤ,+,×) est un cas particulier d'anneau commutatif, correspondant au calcul modulaire sur les restes des entiers dans la division par n. Tout anneau unitaire contient un sous-anneau isomorphe soit à (ℤ/nℤ,+,×) soit à l'anneau (ℤ,+,×) des entiers.

Nouveau!!: Test de primalité de Miller-Rabin et Anneau ℤ/nℤ · Voir plus »

Éditions Dunod

Dunod est une maison d'édition du groupe Hachette Livre, spécialisée dans les ouvrages de formation universitaire et professionnelle et regroupe les marques Dunod, Armand Colin, InterÉditions, Ediscience, ETSF.

Nouveau!!: Test de primalité de Miller-Rabin et Éditions Dunod · Voir plus »

Belin éditeur

Belin éditeur est une maison d'édition française, fondée en 1777 et spécialisée dans les ouvrages universitaires, scolaires et parascolaires.

Nouveau!!: Test de primalité de Miller-Rabin et Belin éditeur · Voir plus »

Chiffrement RSA

Ronald Rivest (2015). Adi Shamir (2013). Leonard Adleman (2010). Le chiffrement RSA (nommé par les initiales de ses trois inventeurs) est un algorithme de cryptographie asymétrique, très utilisé dans le commerce électronique, et plus généralement pour échanger des données confidentielles sur Internet.

Nouveau!!: Test de primalité de Miller-Rabin et Chiffrement RSA · Voir plus »

Comparaison asymptotique

Comparaison asymptotique des fonctions utilisées en informatique plus précisément en algorithme. On voit par exemple que la fonction exponentielle (2^n) croit plus vite que la fonction linéaire (n). En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier la vitesse de croissance d'une fonction.

Nouveau!!: Test de primalité de Miller-Rabin et Comparaison asymptotique · Voir plus »

Congruence sur les entiers

La congruence sur les entiers est une relation pouvant unir deux entiers.

Nouveau!!: Test de primalité de Miller-Rabin et Congruence sur les entiers · Voir plus »

Corps (mathématiques)

En mathématiques, un corps est une des structures algébriques fondamentales de l'algèbre générale.

Nouveau!!: Test de primalité de Miller-Rabin et Corps (mathématiques) · Voir plus »

Corps fini

En mathématiques et plus précisément en algèbre, un corps fini est un corps commutatif qui est par ailleurs fini.

Nouveau!!: Test de primalité de Miller-Rabin et Corps fini · Voir plus »

CRC Press

CRC Press est une société spécialisée dans la publication de livres techniques et scientifiques dans de très nombreux domaines de recherche.

Nouveau!!: Test de primalité de Miller-Rabin et CRC Press · Voir plus »

Cryptographie

La machine de Lorenz utilisée par les nazis durant la Seconde Guerre mondiale pour chiffrer les communications militaires de haut niveau entre Berlin et les quartiers-généraux des différentes armées. La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés.

Nouveau!!: Test de primalité de Miller-Rabin et Cryptographie · Voir plus »

Cryptographie asymétrique

Schéma du chiffrement asymétrique: une clé sert à chiffrer et une seconde à déchiffrer La cryptographie asymétrique, ou cryptographie à clé publique est un domaine relativement récent de la cryptographie.

Nouveau!!: Test de primalité de Miller-Rabin et Cryptographie asymétrique · Voir plus »

Cryptosystème de ElGamal

Le cryptosystème d'ElGamal, ou chiffrement El Gamal (ou encore système d'El Gamal) est un protocole de cryptographie asymétrique inventé par Taher Elgamal en 1984 et construit à partir du problème du logarithme discret.

Nouveau!!: Test de primalité de Miller-Rabin et Cryptosystème de ElGamal · Voir plus »

Digital Signature Algorithm

Le Digital Signature Algorithm, plus connu sous le sigle DSA, est un algorithme de signature numérique standardisé par le NIST aux États-Unis, du temps où le RSA était encore breveté.

Nouveau!!: Test de primalité de Miller-Rabin et Digital Signature Algorithm · Voir plus »

Entier naturel

En mathématiques, un entier naturel est un nombre permettant fondamentalement de compter des objets considérés comme des unités équivalentes: un jeton, deux jetons… une carte, deux cartes, trois cartes… Un tel nombre entier peut s'écrire avec une suite finie de chiffres en notation décimale positionnelle (sans signe et sans virgule).

Nouveau!!: Test de primalité de Miller-Rabin et Entier naturel · Voir plus »

Exponentiation modulaire

En mathématiques, plus précisément en arithmétique modulaire, l’exponentiation modulaire est un type d'élévation à la puissance (exponentiation) réalisée sur des entiers modulo un entier.

Nouveau!!: Test de primalité de Miller-Rabin et Exponentiation modulaire · Voir plus »

Exponentiation rapide

En informatique, l'exponentiation rapide est un algorithme utilisé pour calculer rapidement de grandes puissances entières.

Nouveau!!: Test de primalité de Miller-Rabin et Exponentiation rapide · Voir plus »

Factorisation

En mathématiques, la factorisation consiste à écrire une expression algébrique (notamment une somme), un nombre, une matrice sous la forme d'un produit.

Nouveau!!: Test de primalité de Miller-Rabin et Factorisation · Voir plus »

Faux positif

Un faux positif est le résultat d'une prise de décision dans un choix à deux possibilités (positif et négatif), déclaré positif, là où il est en réalité négatif.

Nouveau!!: Test de primalité de Miller-Rabin et Faux positif · Voir plus »

Gary L. Miller

Gary Lee Miller est un professeur d'informatique à l'université Carnegie-Mellon, à Pittsburgh, aux États-Unis.

Nouveau!!: Test de primalité de Miller-Rabin et Gary L. Miller · Voir plus »

GNU MP

GNU MP, également appelée GMP, est une bibliothèque logicielle de calcul multiprécision sur des nombres entiers, rationnels et en virgule flottante.

Nouveau!!: Test de primalité de Miller-Rabin et GNU MP · Voir plus »

Hypothèse de Riemann généralisée

L'hypothèse de Riemann est l'une des plus importantes conjectures des mathématiques et concerne les zéros de la fonction ζ de Riemann.

Nouveau!!: Test de primalité de Miller-Rabin et Hypothèse de Riemann généralisée · Voir plus »

Indicatrice d'Euler

''φ''(''n''). En mathématiques, l'indicatrice d'Euler est une fonction arithmétique de la théorie des nombres, qui à tout entier naturel non nul associe le nombre d'entiers compris entre 1 et (inclus) et premiers avec.

Nouveau!!: Test de primalité de Miller-Rabin et Indicatrice d'Euler · Voir plus »

Logarithme discret

Le logarithme discret est un objet mathématique utilisé en cryptologie.

Nouveau!!: Test de primalité de Miller-Rabin et Logarithme discret · Voir plus »

Louis Monier (programmeur)

Louis Monier, né en 1956, est un chercheur et programmeur américain d'origine française, fondateur du moteur de recherche AltaVista, avec Paul Flaherty et Michael Burrows.

Nouveau!!: Test de primalité de Miller-Rabin et Louis Monier (programmeur) · Voir plus »

Mathématiques

Les mathématiques (ou la mathématique) sont un ensemble de connaissances abstraites résultant de raisonnements logiques appliqués à des objets divers tels que les ensembles mathématiques, les nombres, les formes, les structures, les transformations; ainsi qu'aux relations et opérations mathématiques qui existent entre ces objets.

Nouveau!!: Test de primalité de Miller-Rabin et Mathématiques · Voir plus »

Méthode de Monte-Carlo

Une méthode de Monte-Carlo, ou méthode Monte-Carlo, est une méthode algorithmique visant à calculer une valeur numérique approchée en utilisant des procédés aléatoires, c'est-à-dire des techniques probabilistes.

Nouveau!!: Test de primalité de Miller-Rabin et Méthode de Monte-Carlo · Voir plus »

Michael Rabin

Michael Oser Rabin, né le à Breslau en Allemagne, maintenant Wrocław en Pologne) est un informaticien et un logicien israélien. Il a été récipiendaire du prix Turing, la récompense la plus prestigieuse en informatique.

Nouveau!!: Test de primalité de Miller-Rabin et Michael Rabin · Voir plus »

MIT Press

MIT Press (pouvant se traduire en français par « presses du MIT ») est une maison d'édition universitaire américaine affiliée au Massachusetts Institute of Technology à Cambridge, Massachusetts.

Nouveau!!: Test de primalité de Miller-Rabin et MIT Press · Voir plus »

National Institute of Standards and Technology

Le National Institute of Standards and Technology (NIST), est une agence du département du Commerce des États-Unis.

Nouveau!!: Test de primalité de Miller-Rabin et National Institute of Standards and Technology · Voir plus »

Nombre composé

Un nombre composé est un entier naturel différent de 0 qui possède un diviseur positif autre que 1 ou lui-même.

Nouveau!!: Test de primalité de Miller-Rabin et Nombre composé · Voir plus »

Nombre de Carmichael

Robert Daniel Carmichael En théorie des nombres, un nombre de Carmichael (portant le nom du mathématicien américain Robert Daniel Carmichael), ou nombre absolument pseudo-premier, est un nombre composé n qui vérifie la propriété suivante, satisfaite par tous les nombres premiers d'après le petit théorème de Fermat: C'est donc un nombre pseudo-premier de Fermat en toute base première avec lui (on peut d'ailleurs se restreindre aux entiers a de 2 à n-1 dans cette définition).

Nouveau!!: Test de primalité de Miller-Rabin et Nombre de Carmichael · Voir plus »

Nombre premier

Entiers naturels de zéro à cent. Les nombres premiers sont marqués en rouge. 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.

Nouveau!!: Test de primalité de Miller-Rabin et Nombre premier · Voir plus »

Nombre pseudo-premier

Un nombre pseudo-premier est un nombre premier probable (un entier naturel qui partage une propriété commune à tous les nombres premiers) qui n'est en fait pas premier.

Nouveau!!: Test de primalité de Miller-Rabin et Nombre pseudo-premier · Voir plus »

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.

Nouveau!!: Test de primalité de Miller-Rabin et P (complexité) · Voir plus »

Parité (arithmétique)

En arithmétique modulaire, étudier la parité d'un entier, c'est déterminer si cet entier est ou non un multiple de deux.

Nouveau!!: Test de primalité de Miller-Rabin et Parité (arithmétique) · Voir plus »

Petit théorème de Fermat

En mathématiques, le petit théorème de Fermat est un résultat de l'arithmétique modulaire, qui peut aussi se démontrer avec les outils de l'arithmétique élémentaire.

Nouveau!!: Test de primalité de Miller-Rabin et Petit théorème de Fermat · Voir plus »

Probabilité conditionnelle

320x320px En théorie des probabilités, une probabilité conditionnelle est la probabilité d'un événement sachant qu'un autre événement a eu lieu.

Nouveau!!: Test de primalité de Miller-Rabin et Probabilité conditionnelle · Voir plus »

Proposition contraposée

En mathématiques et en logique, la contraposition transforme une implication « si A alors B » en une implication équivalente « si non B alors non A ».

Nouveau!!: Test de primalité de Miller-Rabin et Proposition contraposée · Voir plus »

Racine carrée

Pas de description.

Nouveau!!: Test de primalité de Miller-Rabin et Racine carrée · Voir plus »

Springer Science+Business Media

Springer Science+Business Media ou Springer (anc. Springer Verlag) est un groupe éditorial et de presse spécialisée d'origine allemande.

Nouveau!!: Test de primalité de Miller-Rabin et Springer Science+Business Media · Voir plus »

Test de primalité

date.

Nouveau!!: Test de primalité de Miller-Rabin et Test de primalité · Voir plus »

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

Nouveau!!: Test de primalité de Miller-Rabin et Test de primalité AKS · Voir plus »

Test de primalité de Fermat

Si le test de Fermat échoue, alors le nombre est composé. Si le test réussit, il y a de fortes chances que le nombre soit premier (illustration inspirée de, p. 30). En algorithmique, le test de primalité de Fermat est un test de primalité probabiliste basé sur le petit théorème de Fermat.

Nouveau!!: Test de primalité de Miller-Rabin et Test de primalité de Fermat · Voir plus »

Test de primalité de Solovay-Strassen

Le test de primalité de Solovay-Strassen, dû à Robert Solovay et Volker Strassen, est un test de primalité, c'est-à-dire un procédé qui détermine si un nombre impair est composé ou premier.

Nouveau!!: Test de primalité de Miller-Rabin et Test de primalité de Solovay-Strassen · Voir plus »

Théorème des nombres premiers

Une illustration du théorème des nombres premiers: en rouge, le nombre de nombres premiers inférieurs ou égaux à x; en vert, une approximation utilisant \fracx\lnx; en bleu, une approximation utilisant l'intégrale logarithmique \operatornameLi(x). En mathématiques, et plus précisément en théorie analytique des nombres, le théorème des nombres premiers, démontré indépendamment par Hadamard et La Vallée Poussin en 1896, est un résultat concernant la distribution asymptotique des nombres premiers.

Nouveau!!: Test de primalité de Miller-Rabin et Théorème des nombres premiers · Voir plus »

Redirections ici:

Test de primalite de Miller-Rabin, Test de primalité de miller-rabin.

SortantEntrants
Hey! Nous sommes sur Facebook maintenant! »