Maximal Quotient Rational Reconstruction: An Almost Optimal Algorithm for Rational Reconstruction

Let n/d ∈ Q, m be a positive integer and let u = n/d mod m. Thus u is the image of a rational number modulom. The rational reconstruction problem is; given u and m find n/d. A solution was first given by Wang in 1981. Wang’s algo-rithm outputs n/d when m> 2M2 where M = max(|n|, d). Because of the wide application of this algorithm in com-puter algebra, several authors have investigated its practical efficiency and asymptotic time complexity. In this paper we present a new solution which is almost optimal in the following sense; with controllable high prob-ability, our algorithm will output n/d when m is a modest number of bits longer than 2|n|d. This means that in a mod-ular algorithm where m is a product of primes, the modular algorithm will need one or two primes more than the mini-mum necessary to reconstruct n/d; thus if |n | ¿ d or d ¿ |n| the new algorithm saves up to half the number of primes. Further, our algorithm will fail with high probability when m < 2|n|d