General  Information
Important Dates
Conference Poster
Organizing Committee
Program and Schedule
Invited Talks
Contributed Talks
Software Exhibitions
Registered Participants
 Call  For
Research Papers
Software Exhibitions
Jenks Prize Nominations
 Local  Information
Conference Location
Speakers' Information
Gastronomic Guide
Additional Information
Social Events
Previous ISSACs
Other Events



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

M. Monagan


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.

  issac2004 @