Acceleration of Euclidean algorithm and extensions

DOI10.1145/780506.780533zbMath1072.68691OpenAlexW2025418297MaRDI QIDQ4660706

Pan, Victor Y., Xinmao Wang

Publication date: 4 April 2005

Published in: Proceedings of the 2002 international symposium on Symbolic and algebraic computation (Search for Journal in Brave)

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

zbMATH Keywords

randomized algorithmslinear system of equationsextended Euclidean algorithm\(p\)-adic liftingToeplitz and Hankel matricesrational number reconstructionbit operation complexitySmith invariant factors

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Randomized algorithms (68W20) Matrices of integers (15B36) Linear equations (linear algebraic aspects) (15A06) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Toeplitz, Cauchy, and related matrices (15B05)

Related Items (3)

An algorithm to solve integer linear systems exactly using numerical methods ⋮ Around the numeric-symbolic computation of differential Galois groups ⋮ On Schönhage's algorithm and subquadratic integer gcd computation

This page was built for publication: Acceleration of Euclidean algorithm and extensions