Given a system of polynomial equations, including equalities and inequalities, with coefficients in the field of rational numbers, we show how to compute a geometric resolution of the set of common roots of the system over the field of complex numbers. A geometric resolution consists of a primitive element of the algebraic extension defined by the set of roots, its minimal polynomial and the parameterizations of the coordinates. Such a representation of the solutions has a long history which goes back to Leopold Kronecker and has been revisited many times in computer algebra.
We give a new generation of probabilistic algorithms where all the computations use only univariate or bivariate polynomials. We introduce a new codification of the set of solutions of a positive dimensional algebraic variety relying on a new global version of Newton's iterator. Roughly speaking the complexity of our algorithm is polynomial in some kind of degree of the system, in its height, and linear in the complexity of evaluation of the system.
We present our implementation in the Magma system which is called Kronecker, in homage to his method for solving systems of polynomial equations. We show that its theoretical complexity is well reflected in practice and we exhibit some cases for which our method is more efficient than the other available softwares.
Compter le nombre de points d'une courbe définie sur un corps
fini est un problème difficile qui intervient naturellement en
théorie des nombres, et qui de plus trouve des applications en
cryptographie.
Pour une droite ou une conique, le calcul est
élémentaire. Pour une courbe elliptique
(genre 1), le problème fut résolu en
théorie par Schoof en 1985, et les améliorations des
10 ans qui ont suivis permettent de traiter tous les
cas raisonnables.
Le cas du genre 2 fut résolu en
théorie par l'algorithme polynomial de Pila, mais en pratique
les algos exponentiels restaient meilleurs.
Nous allons exposer une première implantation d'un algorithme
polynomial pour le calcul du nombre de points en genre 2. Nous
détaillerons en particulier les problèmes liés
aux systèmes polynomiaux qui apparaissent naturellement dans
l'algorithme.
Plan de l'exposé :
Soit k un corps de caractéristique zéro (ou suffisamment grande). On considère un système de n équations à paramètres f1,f2,...,fn de k[p1,...,pm,x1,...,xn] où les variables p1,...,pm sont considérées comme des paramètres et les variables x1,...,xn comme de vraies inconnues.
Supposons que pour une valeur générique des paramètres p, le système soit consistant et admette un nombre fini de solutions (en les variables x). Alors le quotient k(p1,...,pm)[x1,...,xn] / (f1,f2,...,fn) est un k(p1,...,pm)-espace vectoriel de dimension finie, et représente les solutions "génériques" du système f.
Sous une hypothèse supplémentaire de radicalité, nous donnons un algorithme qui calcule une résolution géométrique de ces zéros génériques, i.e. une représentation univariée des solutions, dont les coefficients sont des fractions rationnelles en les paramètres. Des exemples de diverses provenances viendront illustrer le propos.
Soit K un corps commutatif quelconque. Une algèbre de quaternions H de centre K est une algèbre centrale de dimension 4 sur K telle qu'il existe une algèbre L séparable de dimension 2 sur K et un élément inversible q de K avec: H=L+Lu, où uÎ H vérifie:
où
u2=q, um=
m u pour tout m Î L, est le K-automorphisme non trivial de L. L'exemple fondamental d'une telle algèbre sur K est donné par l'algèbre M(2,K) des matrices carrées d'ordre 2 à coefficients dans K.
m®
m Leurs applications en théorie des nombres sont multiples. Par exemple, en 1986, M. Rabin et J. Shallit présentaient un algorithme probabiliste basé sur la théorie générale des quaternions pour décomposer n en une somme de quatre carrés n=a2+b2+c2+d2.
Un des charmes de la théorie combinatoire des nombres réside dans la diversité (pour ne pas dire le fouillis) qui y règne. J'essaierai, à travers différents problèmes classiques, de faire voyager l'auditeur dans quelques méandres de la théorie qui nous emmèneront de la combinatoire au codage en passant par la théorie des nombres et l'analyse.
L'identifiabilité structurelle est un problème courant de modélisation; il s'agit de savoir si les paramètres d'un modèle peuvent être déterminés à partir de mesures expérimentales et de conditions initiales.
L'algèbre différentielle initiée par J.F. Ritt permet une formulation élégante et effective de ce problème. Les algorithmes de calcul formel existant dans ce domaine sont malheureusement difficilement applicables en pratique.
Nous proposons un algorithme probabiliste mêlant calcul formel et calcul numérique qui permet de tester l'identifiabilité. Sa complexité, exprimée en nombre d'opérations arithmétiques, est polynomiale en toutes les quantités significatives du système.
De manière semblable au cas polynomial, une théorie de Galois différentielle s'est développée. Cela consiste à associer un groupe linéaire à une équation différentielle linéaire. Cette correspondance et l'étude des sous-groupes du groupe de Galois permettent de restreindre la recherche de solutions d'équations différentielles linéaires à des solutions d'une forme très précise.