ComputationA computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computations are mathematical equations and computer algorithms. Mechanical or electronic devices (or, historically, people) that perform computations are known as computers. The study of computation is the field of computability, itself a sub-field of computer science. The notion that mathematical statements should be ‘well-defined’ had been argued by mathematicians since at least the 1600s, but agreement on a suitable definition proved elusive.
Temps de calcul pseudo-polynomialEn informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée). Considérons le problème du test de primalité. On peut vérifier qu'un entier naturel donné n est premier en testant qu'il n'est divisible par aucun des entiers . Cela exige divisions, de sorte que le temps pris par cet algorithme naïf est linéaire en la valeur n .
Décomposition des idéaux premiers dans les extensions galoisiennesEn mathématiques, l'interaction entre le groupe de Galois G d'une extension galoisienne de corps de nombres L/K (ou de corps de nombres p-adiques, ou de corps de fonctions), et la manière dont les idéaux premiers de l'anneau O des entiers se décomposent sous forme de produits d'idéaux premiers de O, est à la base de nombreux développements fructueux en théorie algébrique des nombres. Le cas d'une extension non nécessairement galoisienne est traitée dans l'article « Décomposition des idéaux premiers ».
Corps commutatifvignette|Corps commutatif (pour n premier) En mathématiques, un corps commutatif (parfois simplement appelé corps, voir plus bas, ou parfois appelé champ) est une des structures algébriques fondamentales de l'algèbre générale. C'est un ensemble muni de deux opérations binaires rendant possibles les additions, soustractions, multiplications et divisions. Plus précisément, un corps commutatif est un anneau commutatif dans lequel l'ensemble des éléments non nuls est un groupe commutatif pour la multiplication.
Model of computationIn computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.
Caractéristique d'un anneauEn algèbre, la caractéristique d'un anneau (unitaire) A est par définition l'ordre pour la loi additive de l'élément neutre de la loi multiplicative si cet ordre est fini ; si cet ordre est infini, la caractéristique de l'anneau est par définition zéro. On note, pour un anneau unitaire (A, +, ×), 0A l'élément neutre de « + » et 1A celui de « × ». La caractéristique d'un anneau A est donc le plus petit entier n > 0 tel que si un tel entier existe. Dans le cas contraire (autrement dit si 1A est d'ordre infini), la caractéristique est nulle.
Cryptographie sur les courbes elliptiquesLa cryptographie sur les courbes elliptiques (en anglais, elliptic curve cryptography ou ECC) regroupe un ensemble de techniques cryptographiques qui utilisent une ou plusieurs propriétés des courbes elliptiques, ou plus généralement d'une variété abélienne. L'usage des courbes elliptiques en cryptographie a été suggéré, de manière indépendante, par Neal Koblitz et Victor S. Miller en 1985.
Fonction récursive primitiveEn théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas de récursion primitive (ou bornée) et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. Elles ont été initialement analysées par la mathématicienne Rózsa Péter. On s'intéresse aux fonctions définies sur l'ensemble des entiers naturels, ou sur les ensembles des -uplets d'entiers naturels, et à valeurs dans .
Fonction récursiveEn informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini. En fait, cela fait référence à deux concepts liés, mais distincts. En théorie de la calculabilité, la classe des fonctions récursives est une classe plus générale que celle des fonctions récursives primitives, mais plus restreinte que celle des fonctions semi-calculables (ou partielles récursives).
Primitive polynomial (field theory)In finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field GF(pm). This means that a polynomial F(X) of degree m with coefficients in GF(p) = Z/pZ is a primitive polynomial if it is monic and has a root α in GF(pm) such that is the entire field GF(pm). This implies that α is a primitive (pm − 1)-root of unity in GF(pm). Because all minimal polynomials are irreducible, all primitive polynomials are also irreducible.
