If u is an integer, the iratrecon routine reconstructs a signed rational number from its image u modulo m.  The routine applies recursively to the coefficients of polynomials, and to the entries of lists, vectors, and matrices. It returns FAIL if reconstruction does not succeed.

The optional last argument scaled reconstructs all rationals over a common denominator.  This is faster and appropriate for modular algorithms.

There are two algorithms for recovering rational numbers.  Wang's algorithm (the default) uses bounds N and D on the numerator and denominator. If these are not specified, both bounds default to the largest integer $i$ satisfying $2i^2<m$.  The condition $2\mathrm{ND}<m$ implies a unique answer.

The optional third argument maxquo specifies that Monagan's maximal quotient algorithm should be used.  This algorithm reconstructs $\frac{n}{d}$ with high probability when the modulus $m$ is only a modest number of bits longer than $2\left|n\right|d$, the minimum possible.  The algorithm returns the rational corresponding to the largest quotient in the Euclidean algorithm, provided that quotient is larger than a bound Q.  If Q is not specified it defaults to $2{\mathrm{ilog2}\left(m\right)}^3$, which yields a probability of error that is approximately $\frac{1}{{\mathrm{ilog2}\left(m\right)}^2}$.  If $9n^2{d}^2<m$ then the algorithm always returns $\frac{n}{d}$.

An optional six argument syntax specifies all bounds and iratrecon returns true or false to indicate whether reconstruction was successful. On success, the numerator and common denominator are assigned to the 5th and 6th arguments.  This syntax implies the scaled option and offers the best performance.

$m≔13$

$m≔13$

$u≔\frac{1}{2}\mathbf{mod}m$

$u≔7$

$\mathrm{iratrecon}\left(u\&comma;m\right)$

$\frac{1}{2}$

$\mathrm{iratrecon}\left(u\&comma;m\&comma;2\&comma;2\right)$

$\frac{1}{2}$

$u≔\frac{1}{3}\mathbf{mod}m$

$u≔9$

$\mathrm{iratrecon}\left(u\&comma;m\right)$

$\mathrm{FAIL}$

$\mathrm{iratrecon}\left(u\&comma;m\&comma;\mathrm{maxquo}\right)$

$\mathrm{FAIL}$

$\mathrm{iratrecon}\left(u\&comma;m\&comma;\mathrm{maxquo}\&comma;1\right)$

$\frac{1}{3}$

$U≔\left[0\&comma;1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;7\&comma;8\&comma;9\&comma;10\&comma;11\&comma;12\right]$

$U≔\left[0\&comma;1\&comma;2\&comma;3\&comma;4\&comma;5\&comma;6\&comma;7\&comma;8\&comma;9\&comma;10\&comma;11\&comma;12\right]$

$\mathrm{map}\left(\mathrm{iratrecon}\&comma;U\&comma;m\right)$

$\left[0\&comma;1\&comma;2\&comma;\mathrm{FAIL}\&comma;\mathrm{FAIL}\&comma;\mathrm{FAIL}\&comma;-\frac{1}{2}\&comma;\frac{1}{2}\&comma;\mathrm{FAIL}\&comma;\mathrm{FAIL}\&comma;\mathrm{FAIL}\&comma;\mathrm{-2}\&comma;\mathrm{-1}\right]$

$\mathrm{map}\left(\mathrm{iratrecon}\&comma;U\&comma;m\&comma;2\&comma;3\right)$

$\left[0\&comma;1\&comma;2\&comma;\mathrm{FAIL}\&comma;-\frac{1}{3}\&comma;\frac{2}{3}\&comma;-\frac{1}{2}\&comma;\frac{1}{2}\&comma;-\frac{2}{3}\&comma;\frac{1}{3}\&comma;\mathrm{FAIL}\&comma;\mathrm{-2}\&comma;\mathrm{-1}\right]$

$\mathrm{map}\left(\mathrm{iratrecon}\&comma;U\&comma;m\&comma;3\&comma;2\right)$

$\left[0\&comma;1\&comma;2\&comma;3\&comma;\mathrm{FAIL}\&comma;-\frac{3}{2}\&comma;-\frac{1}{2}\&comma;\frac{1}{2}\&comma;\frac{3}{2}\&comma;\mathrm{FAIL}\&comma;\mathrm{-3}\&comma;\mathrm{-2}\&comma;\mathrm{-1}\right]$

$m≔19$

$m≔19$

$a≔\frac{1}{2}x-\frac{2}{3}\mathbf{mod}m$

$a≔10x+12$

$\mathrm{iratrecon}\left(a\&comma;m\right)$

$\frac{x}{2}-\frac{2}{3}$

$m≔89\cdot 97\cdot 101\cdot 103$

$m≔89809099$

$f≔1234567891+\frac{1}{987654321}x+\frac{97531}{8642}y$

$f≔1234567891+\frac{x}{987654321}+\frac{97531y}{8642}$

$$\begin{gathered} \mathbf{for}p\mathbf{in}\left[107\&comma;109\&comma;113\&comma;127\&comma;131\&comma;139\&comma;151\right]\mathbf{do} \\ m≔mp; \\ u≔f\mathbf{mod}m; \\ \mathrm{print}\left(p\&comma;\mathrm{iratrecon}\left(u\&comma;m\right)\&comma;\mathrm{iratrecon}\left(u\&comma;m\&comma;\mathrm{maxquo}\right)\right) \\ \mathbf{end}\mathbf{do}\&colon; \end{gathered}$$

$107,\mathrm{FAIL},\mathrm{FAIL}$

$109,\mathrm{FAIL},\mathrm{FAIL}$

$113,-\frac{107651}{7573928}-\frac{2276972x}{6358627}+\frac{97531y}{8642},\mathrm{FAIL}$

$127,\mathrm{FAIL},1234567891+\frac{x}{987654321}+\frac{97531y}{8642}$

$131,\mathrm{FAIL},1234567891+\frac{x}{987654321}+\frac{97531y}{8642}$

$139,1234567891+\frac{x}{987654321}+\frac{97531y}{8642},1234567891+\frac{x}{987654321}+\frac{97531y}{8642}$

$151,1234567891+\frac{x}{987654321}+\frac{97531y}{8642},1234567891+\frac{x}{987654321}+\frac{97531y}{8642}$

$\mathrm{iratrecon}\left(9\&comma;13\&comma;3\&comma;3\right)$

$\frac{1}{3}$

$\mathrm{iratrecon}\left(9\&comma;13\&comma;4\&comma;4\right)$

$\mathrm{-4}$

$v≔\mathrm{Vector}\left(\left[\frac{12345}{41}\&comma;-\frac{3457}{82}\&comma;\frac{457}{123}\right]\right)$

$v≔\left[\begin{array}{c}\frac{12345}{41}\\ -\frac{3457}{82}\\ \frac{457}{123}\end{array}\right]$

$m≔46327\cdot 46309$

$m≔2145357043$

$u≔v\mathbf{mod}m$

$u≔\left[\begin{array}{c}575583898\\ 2014542547\\ 2075589338\end{array}\right]$

$\mathrm{iratrecon}\left(u\&comma;m\&comma;\mathrm{scaled}\right)$

$\left[\begin{array}{c}\frac{12345}{41}\\ -\frac{3457}{82}\\ \frac{457}{123}\end{array}\right]$

$\mathrm{iratrecon}\left(u\&comma;m\&comma;32000\&comma;32000\&comma;'\mathrm{num}'\&comma;'\mathrm{den}'\right)$

$\mathrm{true}$

$\mathrm{num}$

$\left[\begin{array}{c}74070\\ \mathrm{-10371}\\ 914\end{array}\right]$

$\mathrm{den}$

$246$

$\frac{\mathrm{num}}{\mathrm{den}}$

$\left[\begin{array}{c}\frac{12345}{41}\\ -\frac{3457}{82}\\ \frac{457}{123}\end{array}\right]$

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.