Test de primalité de Fermatvignette|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. Il est de type Monte-Carlo : s'il détecte qu'un nombre est composé alors il a raison ; en revanche, il peut se tromper s'il prétend que le nombre est premier.
Nombre premier probableEn 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.
Test de primalité AKSLe 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 ».
Fermat pseudoprimeIn number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For an integer a > 1, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a. In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes the Fermat primality test for the base a.
Algorithme probabilisteEn 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].
Petit théorème de FermatEn 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. Il s'énonce comme suit : « si p est un nombre premier et si a est un entier non divisible par p, alors ap–1 – 1 est un multiple de p », autrement dit (sous les mêmes conditions sur a et p), ap–1 est congru à 1 modulo p : Un énoncé équivalent est : « si p est un nombre premier et si a est un entier quelconque, alors ap – a est un multiple de p » : Il doit son nom à Pierre de Fermat, qui l'énonce pour la première fois en .
Crible d'ÉratosthèneLe crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. Le crible d'Atkin est plus rapide mais plus complexe. L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de 2 à N tous les multiples d'un entier (autres que lui-même). En supprimant tous ces multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier à part 1 et eux-mêmes, et qui sont donc les nombres premiers.
Nombre de Carmichaelvignette|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 : pour tout entier a premier avec n, n est un diviseur de a – 1. 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).
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. Par définition, chaque entier plus grand que 1 est donc soit un nombre premier, soit un nombre composé, et les nombres 0 et 1 ne sont ni premiers ni composés. Autre définition : un nombre composé est le produit d'au moins deux nombres premiers (qu'ils soient distincts ou identiques). Par exemple, l'entier 14 est un nombre composé parce qu'il a les nombres 1, 2, 7 et 14 pour diviseurs (quatre diviseurs).
Complexité en tempsEn 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 de Fermatthumb|Le mathématicien français Pierre de Fermat (1601-1665) étudia les propriétés des nombres portant maintenant son nom. Un nombre de Fermat est un nombre qui peut s'écrire sous la forme 22n + 1, avec n entier naturel. Le n-ième nombre de Fermat, 22n + 1, est noté Fn. Ces nombres doivent leur nom à Pierre de Fermat, qui émit la conjecture que tous ces nombres étaient premiers. Cette conjecture se révéla fausse, F5 étant composé, de même que tous les suivants jusqu'à F32.
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.
Primality certificateIn mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. "Succinct" usually means that the proof should be at most polynomially larger than the number of digits in the number itself (for example, if the number has b bits, the proof might contain roughly b2 bits).
Carl PomeranceCarl Pomerance (né en 1944 à Joplin, Missouri) est un théoricien des nombres américain, particulièrement productif et connu dans son domaine de recherche. Il fut élève à l'université Brown et reçut son doctorat à Harvard en 1972. Sa thèse prouva que tout nombre parfait impair contient au moins sept facteurs premiers distincts. Il rejoignit immédiatement la faculté à l'université de Géorgie et devint professeur en 1982. Il travailla ensuite pour la firme Lucent durant plusieurs années puis fut nommé Distinguished Professor au Dartmouth College.
Algorithme de ShorEn arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique conçu par Peter Shor en 1994, qui factorise un entier naturel N en temps O et en espace . Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implanté dans un calculateur quantique pratique. Un message chiffré avec RSA peut être déchiffré par factorisation de sa clé publique N, qui est le produit de deux nombres premiers.
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).
Symbole de Jacobivignette|Charles Jacobi, mathématicien à l'origine du symbole de Jacobi Le symbole de Jacobi est utilisé en mathématiques dans le domaine de la théorie des nombres. Il est nommé ainsi en l'honneur du mathématicien prussien Charles Gustave Jacob Jacobi. C'est une généralisation du symbole de Legendre. Le symbole de Jacobi est défini pour tout entier relatif et tout entier naturel impair comme produit de symboles de Legendre, en faisant intervenir la décomposition en facteurs premiers de : pour tout et tous nombres premiers impairs (non nécessairement distincts), Soient positifs impairs et entiers quelconques.
Entier sans facteur carrévignette|Les nombres qui n'ont pas été rayé sont tous les entiers sans facteur carré jusqu'à 120 En mathématiques et plus précisément en arithmétique, un entier sans facteur carré (souvent appelé, par tradition ou commodité quadratfrei ou squarefree) est un entier relatif qui n'est divisible par aucun carré parfait, excepté 1. Par exemple, 10 est sans facteur carré mais 18 ne l'est pas, puisqu'il est divisible par 9 = 3. Les dix plus petits nombres de la des entiers positifs sans facteur carré sont 1, 2, 3, 5, 6, 7, 10, 11, 13, 14.
L (complexité)En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE.
Multiplicative group of integers modulo nIn modular arithmetic, the integers coprime (relatively prime) to n from the set of n non-negative integers form a group under multiplication modulo n, called the multiplicative group of integers modulo n. Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n. Hence another name is the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo n.
