# Séminaire interne du LIX Année 99-00

Retour à la page actuelle du séminaire.
• A Gröbner Free Alternative for Polynomial Systems Solving Grégoire Lecerf Mardi 9 Novembre 1999, 14H
(Travail en collaboration avec Marc Giusti et Bruno Salvy)

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.

• Algorithme de Schoof pour les courbes de genre 2. Pierrick Gaudry Vendredi 4 Février 2000 à 10H30

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é :

1. Motivation de l'algorithme.
2. Jacobiennes de courbes en genre 2
3. Lifting de la 2 torsion
4. Perspectives

• Systèmes polynomiaux (suite) E. Schost Jeudi 24 Février, 10h30

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.

• Algèbres de quaternions: définitions et intérêt. M. Fouquet Jeudi 23 Mars, 10h30

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:

u2=q,   um=  m
u  pour tout  m Î L,
m®  m
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.

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.

• Incitation à la théorie combinatoire des nombres. Alain Plagne Salle de réunion du LIX, Mercredi 5 Avril, 10h30
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.

• Identifiabilité structurelle et techniques d'évaluation. Alexandre Sedoglavic Salle de réunion du LIX, Jeudi 27 Avril, 10h30
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.

• Théorie de Galois différentielle. Anne Fredet Salle de réunion du LIX, Jeudi 8 Juin, 10h30
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.