Academic literature on the topic 'Racines de polynômes dans un corps fini'

Soient K un corps de nombres et p un nombre premier ≥ 5. Notons μp le groupe des racines p-ièmes de l'unité. On définit p comme étant K-régulier si p ne divise pas le nombre de classes du corps K(μp). Sous l'hypothèse que p est K-régulier et inerte dans K, on établit le second cas du théorème de Fermat sur K pour l'exposant p. On utilise pour cela des arguments classiques, ainsi que le théorème de Faltings selon lequel une courbe de genre au moins deux sur K n'a qu'un nombre fini de points K-rationnels. De plus, si K est un corps quadratique imaginaire, distinct de [Formula: see text], on en déduit un énoncé permettant souvent en pratique de démontrer le théorème de Fermat sur K pour un exposant K-régulier donné. Mots-clés: Théorème de Fermat; corps de nombres. Let K be a number field and p a prime number ≥5. Let us denote by μp the group of the pth roots of unity. We define p to be K-regular if p does not divide the class number of the field K(μp). Under the assumption that p is K-regular and inert in K, we establish the second case of Fermat's Last Theorem over K for the exponent p. We use in the proof classical arguments, as well as Faltings' theorem stating that a curve of genus at least two over K has a finite number of K-rational points. Moreover, if K is an imaginary quadratic field, other than [Formula: see text], we deduce a statement which allows often in practice to prove Fermat's Last Theorem over K for a given K-regular exponent.

RésuméSi k est un corps fini, toute fonction f(x1, … , xm) de {0, 1}m dans k s'écrit de manière unique comme un polynôme, à coefficients dans k, de degré un ou zéro en chacune de ses variables ; on peut donc lui associer une fonction f*(x1, … , xm), sa duale inverse, qui exprime les coefficients de son polynôme canonique. Nous considérons l'improbable hypothèse que la classe P(k), formée des suites de fonctions calculables en un nombre d'opérations (additions et multiplications) de croissance polynomialement bornée, soit close par dualité ; nous montrons qu'elle équivaut à une hypothèse bien connue en Théorie de la Complexité sous le nom de P = #pP, où p est la caractéristique de k.Dans une première section, nous exposons ce résultat lorsque k = ℤ/2ℤ, c'est-à-dire dans le cadre des calculs booléens classiques ; sa démonstration évite l'emploi d'un polynôme universel comme le hamiltonien : ses ingrédients sont d'une part la réduction parcimonieuse des circuits aux termes, et d'autre part la constatation que les expressions arithmétiques ont une duale très facile à calculer.Dans la deuxième section, nous traitons le cas général, en introduisant une classe SP(k) obtenue par sommation à partir de la classe P(k) ; nous vérifierons dans la quatrième section l'équivalence des hypothèses SP(k) = P(k) et #pP = P. Nous y définissons également une notion de transformation, dont la dualité est un cas particulier. Les transformations forment un groupe isomorphe à GL2(k), avec un sous-groupe B(k) de transformations que nous qualifions de bénignes, car elles n'ont que peu d'effet sur la complexité des fonctions ; nous montrons que toutes les transformations non-bénignes ont à peu près la même influence sur la complexité des fonctions, sauf si k = F3 ou k = F5 ; dans ces deux cas exceptionnels, la transformation de Fourier joue un rôle particulier.Dans la troisième section, nous considérons des fonctions de km dans k ; nous n'y trouvons pas des classes de complexité vraiment nouvelles, mais seulement un groupe de transformations plus riche.La quatrième section introduit l'égalité #P = P dans le paysage ; quant à la cinquième et dernière, elle examine le lien entre nos résultats et ceux de Guillaume Malod concernant la clôture par fonction-coefficient de diverses classes de complexité pour le calcul des polynômes à la manière de Valiant.Nous nous sommes efforcés de rédiger cet article de manière à ce qu'il puisse être lu par des personnes non spécialisées en algorithmie.

International audience Let $\Gamma$ be a quiver on $n$ vertices $v_1, v_2, \ldots , v_n$ with $g_{ij}$ edges between $v_i$ and $v_j$, and let $\boldsymbol{\alpha} \in \mathbb{N}^n$. Hua gave a formula for $A_{\Gamma}(\boldsymbol{\alpha}, q)$, the number of isomorphism classes of absolutely indecomposable representations of $\Gamma$ over the finite field $\mathbb{F}_q$ with dimension vector $\boldsymbol{\alpha}$. We use Hua's formula to show that the derivatives of $A_{\Gamma}(\boldsymbol{\alpha}, q)$ with respect to $q$, when evaluated at $q = 1$, are polynomials in the variables $g_{ij}$, and we can compute the highest degree terms in these polynomials. The formulas for these coefficients depend on the enumeration of certain families of connected graphs. This note simply gives an overview of these results; a complete account of this research is available on the arXiv and has been submitted for publication. Soit $\Gamma$ un carquois sur $n$ sommets $ v_1, v_2, \ldots , v_n$ avec $g_{ij}$ arêtes entre $v_i$ et $v_j$, et soit $\boldsymbol{\alpha} \in \mathbb{N}^n$. Hua a donné une formule pour $A_{\Gamma}(\boldsymbol{\alpha}, q)$, le nombre de classes d'isomorphisme absolument indécomposables de représentations de $\Gamma$ sur le corps fini $\mathbb{F}_q$ avec vecteur de dimension $\boldsymbol{\alpha}$. Nous utilisons la formule de Hua pour montrer que les dérivées de $A_{\Gamma}(\boldsymbol{\alpha}, q)$ par rapport à $q$, alors évaluée à $q=1$, sont des polynômes dans les variables $g_{ij}$, et on peut calculer les termes de plus haut degré de ces polynômes. Les formules pour ces coefficients dépendent de l'énumération de certaines familles de graphes connectés. Cette note donne simplement un aperçu de ces résultats, un compte rendu complet de cette recherche est disponible sur arXiv et a été soumis pour publication.

Ma thèse apporte des résultats théoriques et pratiques concernant le meilleur algorithme connu - algorithme de schoof-elkies-atkin (sea) - pour le calcul du nombre de points sur une courbe elliptique dans un corps fini de très grande caractéristique. Cela a permis de déterminer le nombre de points d'une courbe sur un corps de caractéristique étant un nombre record. Plus précisément, je décris, tout d'abord, quelques propriétés des polynômes intervenants dans sea (et plus généralement associes à la courbe elliptique e : polynômes de division, polynômes de division exacte, polynômes de semi-division et les polynômes modulaires), en particulier, je donne la forme de leur décomposition en facteurs irréductibles sur le corps de base. De plus, je montre le lien entre la réductibilité des polynômes modulaires et des polynômes de division. D'autre part, dans le cas d'un bon nombre premier, je donne la complexité des différentes déterminations d'une valeur propre du Frobenius de la courbe elliptique et j'accélère la phase finale de cette détermination, en évitant le calcul des ordonnées des points sur la courbe, dans certains cas que l'on précise

Les calculs modulaires entrant en jeu dans les applications en cryptographie asymétrique utilisent le plus souvent un modulo premier standardisé, dont le choix n’est pas toujours libre en pratique. L’amélioration des opérations modulaires est centrale pour l’efficacité et la sécurité de ces primitives. Cette thèse propose de fournir une arithmétique modulaire efficace pour le plus grand nombre de premiers possible, tout en la prémunissant contre certains types d’attaques. Pour ce faire, nous nous intéressons au système PMNS utilisé pour l’arithmétique modulaire, et proposons des méthodes afin d’obtenir de nombreux PMNS pour un premier donné, avec une arithmétique efficace sur les représentations. Nous considérons également la randomisation des calculs modulaires via des algorithmes de type Montgomery et Babaï en exploitant la redondance intrinsèque aux PMNS. Les changements induits de représentation des données au cours du calcul empêchent un attaquant d’effectuer des hypothèses utiles sur ces représentations. Nous présentons ensuite un système hybride, HyPoRes, avec un algorithme améliorant les réductions modulaires pour tout modulo premier. Les nombres sont représentés dans un PMNS avec des coefficients en RNS. La réduction modulaire est plus rapide qu’en RNS classique pour les premiers standardisés pour ECC. En parallèle, nous étudions un type de représentation utilisé pour la résolution réelle de systèmes flous. Nous revisitons l’approche globale de résolution faisant appel à des techniques algébriques classiques et la renforçons. Ces résultats incluent un système réel appelé la transformation réelle qui simplifie les calculs, et la gestion des signes des solutions
Modular computations involved in public key cryptography applications most often use a standardized prime modulo, the choice of which is not always free in practice. The improvement of modular operations is fundamental for the efficiency and safety of these primitives. This thesis proposes to provide an efficient modular arithmetic for the largest possible number of primes, while protecting it against certain types of attacks. For this purpose, we are interested in the PMNS system used for modular arithmetic, and propose methods to obtain many PMNS for a given prime, with an efficient arithmetic on the representations. We also consider the randomization of modular computations via algorithms of type Montgomery and Babaï by exploiting the intrinsic redundancy of PMNS. Induced changes of data representation during the calculation prevent an attacker from making useful assumptions about these representations. We then present a hybrid system, HyPoRes , with an algorithm that improves modular reductions for any prime modulo. The numbers are represented in a PMNS with coefficients in RNS. The modular reduction is faster than in conventional RNS for the primes standardized for ECC. In parallel, we are interested in a type of representation used to compute real solutions of fuzzy systems. We revisit the global approach of resolution using classical algebraic techniques and strengthen it. These results include a real system called the real transform that simplifies computations, and the management of the signs of the solutions