Thierry Combot - Calcul des relations additives et multiplicatives entre les racines d'un polynôme

jeudi 21 nov. 2024, 16:00 → 17:00 Europe/Paris

112

Soit $P\in \mathbb{Q}[x]$ un polynome sans facteur carrés de degré $n$, et dont les coefficients sont de hauteur au plus $h$. Nous présenterons un algorithme pour le calcul des relations linéaires et multiplicatives entre les racines de $P$, qui s'exécute en temps polynomial en $n,h$, alors que les algorithmes connus étaient en temps polynomial en $n!$. Nous verrons aussi comment construire des polynomes ayant beaucoup de relations entre leurs racines. Enfin, nous appliquerons cette approche pour le calcul des intégrales hyperelliptiques: il est possible de tester si une intégrale hyperelliptique est élémentaire probabilistiquement en temps polynomial en le degré et la hauteur des coefficients.