Integer Rational Reconstruction
Michael Monagan, CECM, SFU
Rational reconstruction as a technology was invented by Wang, Guy and Davenport in 1982 for early recovery of the irreducible factors of a polynomial f in Q[x] from the factorization of f mod p^k. Rational reconstruction can applied whenever we have the image u mod m of a polynomial over Q, providied of course m is large enough. Thus it has wide application. For example, modular Grobner bases, modular polynomial GCD computation, and modular linear algebra operations over Q. In the talk I'll describe how it done; it uses the venerable extended Euclidean algorithm. But the algorithm of Wang et. al. may require m to be up to twice as large as is necesssary. Thus if m is a product of primes, half of the primes are wasted. I will present a new rational reconstruction algorithm which requires m to be just a few bits more bits longer than the minimum necessary. The analysis of the new algorithm sheds some new light on the size of the quotients in the Euclidean algorithm.