Hypothèse de RiemannEn mathématiques, l'hypothèse de Riemann est une conjecture formulée en 1859 par le mathématicien allemand Bernhard Riemann, selon laquelle les zéros non triviaux de la fonction zêta de Riemann ont tous une partie réelle égale à 1/2. Sa démonstration améliorerait la connaissance de la répartition des nombres premiers et ouvrirait des nouveaux domaines aux mathématiques. Cette conjecture constitue l'un des problèmes non résolus les plus importants des mathématiques du début du : elle est l'un des vingt-trois fameux problèmes de Hilbert proposés en 1900, l'un des sept problèmes du prix du millénaire et l'un des dix-huit problèmes de Smale.
Théorème de WilsonEn mathématiques, plus précisément en arithmétique élémentaire, le théorème de Wilson énonce qu'un entier p plus grand que 1 est premier si et seulement si la factorielle de p – 1 est congrue à –1 modulo p. Cette caractérisation des nombres premiers est assez anecdotique et ne constitue pas un test de primalité efficace. Son principal intérêt réside dans son histoire et dans la relative simplicité de son énoncé et de ses démonstrations. Ici, le symbole « ! » désigne la fonction factorielle et le symbole « .
Elliptic curve primalityIn mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and de, in 1993. The concept of using elliptic curves in factorization had been developed by H. W.
Test de primalité de Lucas-LehmerLe test de primalité de Lucas-Lehmer est une méthode pour tester la primalité d'un entier n, connaissant les facteurs premiers de n – 1. Un entier n > 2 est premier si et seulement si il existe un entier a, strictement compris entre 1 et n, tel que et, pour tout facteur premier q de n – 1, Par exemple, prenons n = 2017, n – 1 = 2016 = 2×3×7. a = 2 ne convient pas car 2 ≡ 1 (mod n). a = 3 non plus car 3 ≡ 1 (mod n) Essayons a = 5 (pour calculer rapidement mod n les puissances voulues, on peut utiliser la méthode d'exponentiation rapide et de plus, calculer d'abord 5) : Donc 2017 est premier.
Théorie algorithmique des nombresLa théorie algorithmique des nombres ou théorie calculatoire des nombres est une branche des mathématiques et de l'informatique qui essaie de fournir des solutions concrètes et efficaces à des problèmes calculatoires rencontrés en théorie des nombres. Par exemple, le théorème fondamental de l'arithmétique, qui affirme que tout nombre entier se décompose de manière unique en produit de nombres premiers, donne lieu à l'étude d'algorithmes de factorisation efficace.
Crible quadratiqueL'algorithme du crible quadratique est un algorithme de factorisation fondé sur l'arithmétique modulaire. C'est en pratique le plus rapide après le crible général des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci.
Quantum algorithmIn quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer.
Symbole de LegendreEn théorie des nombres, le symbole de Legendre est une fonction de deux variables entières à valeurs dans {–1, 0, 1}, qui caractérise les résidus quadratiques. Il a été introduit par Adrien-Marie Legendre, au cours de ses efforts pour démontrer la loi de réciprocité quadratique. Il ne dépend donc que de la classe de a modulo p. Le cas particulier p = 2 est inclus dans cette définition mais sans intérêt : vaut 0 si a est pair et 1 sinon.
Problème de décisionEn informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat.
Nombre premiervignette|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.
Théorie analytique des nombresdroite|vignette|La fonction zêta de Riemann ζ(s) dans le plan complexe. La couleur d'un point s code la valeur de ζ(s) : les couleurs proches du noir indiquent des valeurs proches de zéro, alors que la teinte code l'argument de la valeur. En mathématiques, la théorie analytique des nombres est une branche de la théorie des nombres qui utilise des méthodes d'analyse mathématique pour résoudre des problèmes concernant les nombres entiers.
Problème algorithmiqueUn problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question. Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier.
