If u is an integer, the iratrecon routine reconstructs a signed rational number from its image u modulo m.

In the first calling sequence, both N (the maximum magnitude of the numerator) and D (the maximum magnitude of the denominator) are chosen to be the largest integer  satisfying .

The iratrecon command then returns, if it exists, the unique rational number  satisfying , , ,  and . Otherwise, iratrecon returns FAIL.

If the rational  we are trying to reconstruct satisfies  and  and the modulus m satisfies  then this algorithm with the default choice for N and D will output  for all moduli .

The second calling sequence allows specification of N and D. Note that to obtain a unique answer, N and D must satisfy , though it is still possible to obtain a (possibly not unique) solution in some cases when .

In the third calling sequence, if the integer Q is specified, iratrecon(u,m,'maxquo',Q) returns, if it exists, a rational number  satisfying ,  such that the quotient  in the Euclidean algorithm corresponding to the rational  is maximal and . Otherwise, iratrecon returns FAIL. If the integer Q is not specified, it defaults to .

If the rational number we are trying to reconstruct is  then one can prove that this algorithm will output  for all moduli .  However, it will output  with high probability for moduli a modest number of bits longer than , the minimum possible.  The default setting of Q means that if iratrecon outputs a rational then the probability that it is wrong is approximately .

To use this routine to reconstruct a rational  from u satisfying , the modulus m used must be chosen to be relatively prime to d. Otherwise, the reconstruction will never succeed.

If the input image u is a polynomial in any number of variables with integer coefficients, iratrecon is applied to the integer coefficients of the polynomial.  If reconstruction fails on a coefficient of a monomial , the implementation remembers this monomial so that next time iratrecon is called on a problem with the same support it will start with the coefficient of the monomial . This means that if iratrecon is being used to reconstruct the rational coefficients of a polynomial using a modular algorithm where the modulus  is increasing, efficiency is not lost on problems with different size of rational coefficients.

If the input image u is a list or vector or matrix of (polynomials of) integers, iratrecon is applied to the entries of the list (or vector or matrix).

If the optional argument scaled is specified, and the input is not a single integer (it is a list or vector or matrix of (polynomials of) integers), if rational reconstruction succeeds in reconstructing the first rational,  say, then it first multiplies the remaining images in  to be reconstructed by  modulo .  This speeds up the reconstruction of the remaining images a lot if the denominators of the remaining rationals are small multiples of  (or vice versa) as is often the case. This option should always be used.

Monagan, M. B. "Maximal Quotient Rational Reconstruction: An Almost Optimal Algorithm for Rational Reconstruction." In Proceedings of ISSAC '04, pp. 243-249. Edited by Jaime Gutierrez. New York: ACM Press, 2004.

Wang, P. S. "Early Detection of True Factors in Univariate Polynomial Factorization." In Proceedings of EUROCAL '83, pp. 225-235. Edited by J. A. van Hulzen. Springer-Verlag, 1983.