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.