Greatest common divisors of polynomials given by straight-line programs

DOI10.1145/42267.45069zbMath0642.68058OpenAlexW2111028162MaRDI QIDQ3783550

Erich L. Kaltofen

Publication date: 1988

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/42267.45069

zbMATH Keywords

greatest common divisorfactorizationstraight-line programsrandomized algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

A quasi-linear irreducibility test in \(\mathbb{K}x[y\)], Computing generators of the ideal of a smooth affine algebraic variety, Sparse polynomial interpolation based on derivatives, Parallel evaluation of arithmetic circuits, Modular composition modulo triangular sets and applications, Straight-line programs in geometric elimination theory, Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs, Sparse interpolation of multivariate rational functions, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, CATEGORICAL COMPLEXITY, On fast multiplication of polynomials over arbitrary algebras, The complexity of two problems on arithmetic circuits, Solving structured linear systems with large displacement rank, Unnamed Item, Evaluation properties of invariant polynomials, Functional decomposition of polynomials: the tame case, Interpolation of polynomials given by straight-line programs, Complexity bounds in elimination theory -- a survey., Computing Puiseux series: a fast divide and conquer algorithm, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, Generalized Wong sequences and their applications to Edmonds' problems