Acceleration of Euclidean Algorithm and Rational Number Reconstruction

DOI10.1137/S0097539702408636zbMath1031.68149OpenAlexW2143852990MaRDI QIDQ4706218

Pan, Victor Y., Xinmao Wang

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539702408636

zbMATH Keywords

bit complexityextended Euclidean algorithm

Mathematics Subject Classification ID

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

Related Items (9)

Certified dense linear system solving ⋮ Binomiality testing and computing sparse polynomials via witness sets ⋮ Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\) ⋮ Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization ⋮ Calculation of Bezout coefficients for a \(k\)-ary GCD algorithm ⋮ An 𝐿(1/3) algorithm for ideal class group and regulator computation in certain number fields ⋮ A \(p\)-adic algorithm for computing the inverse of integer matrices ⋮ Linear programming using limited-precision oracles ⋮ Certified Hermite Matrices from Approximate Roots - Univariate Case

This page was built for publication: Acceleration of Euclidean Algorithm and Rational Number Reconstruction