Journal
SIAM JOURNAL ON COMPUTING
Volume 32, Issue 2, Pages 548-556Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0097539702408636
Keywords
extended Euclidean algorithm; rational number reconstruction
Ask authors/readers for more resources
We accelerate the known algorithms for computing a selected entry of the extended Euclidean algorithm for integers and, consequently, for the modular and numerical rational number reconstruction problems. The acceleration is from quadratic to nearly linear time, matching the known complexity bound for the integer gcd, which our algorithm computes as a special case.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available