iratrecon(u, m, scaled)
iratrecon(u, m, N, D)
iratrecon(u, m, maxquo, Q)
iratrecon(u, m, N, D, num, den)
iratrecon(u, m, maxquo, Q, num, den)
integer or polynomial with integer coefficients (or a list or Vector or Matrix of these)
positive integer (the modulus)
(optional) literal name, must be the last argument
(optional) positive integer bounds satisfying 2ND<m
(optional) positive integer bound
(optional) names assigned the numerator and denominator
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 2⁢i2<m. The condition 2ND<m implies a unique answer.
The optional third argument maxquo specifies that Monagan's maximal quotient algorithm should be used. This algorithm reconstructs nd with high probability when the modulus m is only a modest number of bits longer than 2⁢n⁢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⁢ilog2⁡m3, which yields a probability of error that is approximately 1ilog2⁡m2. If 9⁢n2⁢d2<m then the algorithm always returns nd.
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
u ≔ 12modm
u ≔ 13modm
U ≔ 0,1,2,3,4,5,6,7,8,9,10,11,12
m ≔ 19
a ≔ 1⁢x2−23modm
This example illustrates the improvement (fewer primes needed) of the maximal quotient rational reconstruction algorithm when the rationals being reconstructed when the size of the numerators and denominators are not uniform. The first modulus used is 89*97*101*103*107 which is sufficiently large so that the three rationals appearing in the polynomial do arise in the Euclidean algorithm.
m ≔ 89⋅97⋅101⋅103
f ≔ 1234567891+1⁢x987654321+97531⁢y8642
forpin107,109,113,127,131,139,151dom ≔ m⁢p;u ≔ fmodm;print⁡p,iratrecon⁡u,m,iratrecon⁡u,m,maxquoend do:
As mentioned, N,D not satisfying 2ND<m may be used, but a solution, if returned, is not necessarily unique.
Note that the 13 is also a viable solution for the second query, but −4 is returned instead. This final example is a vector of rationals using the scaled option.
v ≔ Vector⁡1234541,−345782,457123
m ≔ 46327⋅46309
u ≔ vmodm
The common denominator can make it appear as though some numerators exceed the bound, but this is not so when rationals are reduced to lowest terms.
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.
Download Help Document