Concept
Décomposition en produit de facteurs premiers
Concepts associés (31)
Notation L
La notation L est un analogue aux notations de Landau en notation asymptotique. Cette notation a été introduite par Carl Pomerance en 1982 pour comparer différents algorithmes de factorisation et a été généralisée à deux paramètres par Arjen Lenstra et Hendrik Lenstra. Elle est principalement utilisée en théorie algorithmique des nombres, où elle permet de donner une échelle entre les différents algorithmes exponentiels.
Fraction irréductible
Une fraction irréductible est une fraction pour laquelle il n’existe pas de fraction égale ayant des termes plus petits. Autrement dit, une fraction irréductible ne peut pas être simplifiée. La fraction n'est pas irréductible car 12 et 20 sont des multiples de 4 : (simplification par 4). On peut aussi écrire . La fraction est irréductible car 1 est le seul entier positif qui divise à la fois 3 et 5. On peut simplifier une fraction en divisant ses termes successivement par leurs diviseurs communs apparents (que l'on trouve en appliquant les critères de divisibilité par 2, 3, 5).
Méthode de factorisation de Fermat
vignette|Pierre de Fermat En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers d'un entier naturel. L'intuition est la suivante. Tout entier naturel impair N se décompose en la différence de deux carrés : N = a – b. Algébriquement, cette différence se factorise en (a + b)(a – b) et, si ni a + b ni a – b n'est égal à 1, alors ce sont des facteurs non triviaux de N. Il existe une telle représentation pour tout nombre impair composé.
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 ».
Factorisation de Dixon
En arithmétique modulaire, la méthode de factorisation de Dixon (aussi connue comme l'algorithme de Dixon) est un algorithme de décomposition en produit de facteurs premiers à but général. Le crible quadratique est une modification de l'idée de base utilisée dans la méthode de Dixon. L'algorithme a été proposé par John D. Dixon, un mathématicien de l'université Carleton, et publié en 1981. La méthode de Dixon est basée sur la recherche d'une congruence de carrés.
Nombre semi-premier
En arithmétique, un nombre semi-premier ou bi-premier ou 2-presque premier, est le produit de deux nombres premiers non nécessairement distincts. Les dix premiers termes de la suite des nombres semi-premiers () sont 4, 6, 9, 10, 14, 15, 21, 22, 25 et 26. Depuis 2018, le plus grand nombre semi-premier connu, (2 – 1), est logiquement le carré du plus grand nombre premier connu qui est le nombre premier de Mersenne M. Ce carré a plus de de chiffres décimaux.
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. Divers objets géométriques et arithmétiques peuvent être décrits par ce que l'on appelle les fonctions L globales, qui sont similaires formellement à la fonction zêta de Riemann. On peut alors se poser la même question à propos des zéros de ces fonctions L, fournissant diverses généralisations de l'hypothèse de Riemann.
P-adic valuation
In number theory, the p-adic valuation or p-adic order of an integer n is the exponent of the highest power of the prime number p that divides n. It is denoted . Equivalently, is the exponent to which appears in the prime factorization of . The p-adic valuation is a valuation and gives rise to an analogue of the usual absolute value. Whereas the completion of the rational numbers with respect to the usual absolute value results in the real numbers , the completion of the rational numbers with respect to the -adic absolute value results in the p-adic numbers .
Multiplicité (mathématiques)
En mathématiques, on définit pour certaines propriétés la multiplicité d'une valeur ayant cette propriété. Il s'agit en général d'un nombre naturel qui indique « combien de fois » la valeur possède la propriété. Cela est dépourvu de sens en général (on possède une propriété ou on ne la possède pas), mais une interprétation naturelle existe dans certains cas. En général une propriété pour laquelle des multiplicités sont définies détermine un multiensemble de valeurs plutôt qu'un simple ensemble.
Congruence de carrés
En arithmétique modulaire, une congruence de carrés modulo un entier naturel n est une équation de la forme Une telle équation apporte des informations utiles pour essayer de factoriser l'entier n. En effet, Ceci veut dire que n divise le produit (x + y)(x − y) mais ne divise aucun des deux facteurs x + y et x − y, donc x + y et x − y contiennent tous les deux des diviseurs propres de n, que l'on trouve en calculant les PGCD de (x + y, n) et de (x − y, n).