Let n/d be in Q, m be a positive integer and let u = n/d mod m. Thus u is the image of a rational number modulo m. The rational reconstruction problem is; given u and m find n/d. A solution was first given by Wang in 1981. Wang's algorithm outputs n/d when m > 2 M^2 where M = max(|n|,d). Because of the wide application of this algorithm in computer 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 probability, our algorithm will output n/d when m is only a few bits longer than 2 |n| d. Further, our algorithm will fail with high probability when m < 2 |n| d. This means that in a modular algorithm where m is a product of primes, the modular algorithm will need about one prime more than the minimum necessary to reconstruct n/d; thus if |n| << d or d << |n| the new algorithm saves up to half the number of primes.