Acceleration of Euclidean algorithm and extensions

DOI10.1145/780506.780533MaRDI QIDQ4660706zbMATH OpenOpenAlexFDO

Authors Victor Y. Pan, 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

\(p\)-adic liftingbit operation complexityextended Euclidean algorithmlinear system of equationsrandomized algorithmsrational number reconstructionSmith invariant factorsToeplitz and Hankel matrices

Mathematics Subject Classification ID

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

Recommendations

• Acceleration of Euclidean Algorithm and Rational Number Reconstruction
• Efficient rational number reconstruction
• Fast rational function reconstruction
• On Rational Number Reconstruction and Approximation
• Half-GCD and fast rational recovery

Cited in

(9)

• Accelerated shift-and-add algorithms
• New fast Euclidean algorithms
• An algorithm to solve integer linear systems exactly using numerical methods
• Around the numeric-symbolic computation of differential Galois groups
• New binary Euclidean algorithms
• Acceleration of Euclidean Algorithm and Rational Number Reconstruction
• Half-GCD and fast rational recovery
• On Schönhage's algorithm and subquadratic integer gcd computation
• scientific article; zbMATH DE number 5050108 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4660706)