iratrecon - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Group Theory : Numbers : Integer Functions : iratrecon

iratrecon

rational reconstruction

 

Calling Sequence

Parameters

Description

Examples

References

Calling Sequence

iratrecon(u, m)

iratrecon(u, m, N, D)

iratrecon(u, m, maxquo, Q)

Parameters

u

-

integer or polynomial with integer coefficients (or list or Vector or Matrix of these)

m

-

positive integer (the modulus)

N, D

-

(optional) positive integers satisfying 2ND<m

maxquo

-

literal name

Q

-

(optional) positive integer

scaled

-

(optional) literal name

Description

• 

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 i satisfying 2i2<m.

  

The iratrecon command then returns, if it exists, the unique rational number nd satisfying gcdn&comma;d&equals;1, gcdd&comma;m&equals;1, nd&equals;umodm, &verbar;n&verbar;<=N and 0<=d<=D. Otherwise, iratrecon returns FAIL.

  

If the rational nd we are trying to reconstruct satisfies &verbar;n&verbar;<=N and dD and the modulus m satisfies gcdd&comma;m&equals;1 then this algorithm with the default choice for N and D will output nd for all moduli 2maxN&comma;D2<m.

• 

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

• 

In the third calling sequence, if the integer Q is specified, iratrecon(u,m,'maxquo',Q) returns, if it exists, a rational number nd satisfying gcdn,d=1=gcdd,m, nd&equals;umodm such that the quotient q in the Euclidean algorithm corresponding to the rational nd is maximal and Q<q. Otherwise, iratrecon returns FAIL. If the integer Q is not specified, it defaults to 2ilog2m3.

  

If the rational number we are trying to reconstruct is nd then one can prove that this algorithm will output nd for all moduli m>9n2d2.  However, it will output nd with high probability for moduli a modest number of bits longer than 2&verbar;n&verbar;d, the minimum possible.  The default setting of Q means that if iratrecon outputs a rational then the probability that it is wrong is approximately 1ilog2m2.

• 

To use this routine to reconstruct a rational r&equals;nd from u satisfying r&equals;umodm, 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 t, 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 t. This means that if iratrecon is being used to reconstruct the rational coefficients of a polynomial using a modular algorithm where the modulus m 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, nd say, then it first multiplies the remaining images in u to be reconstructed by d modulo m.  This speeds up the reconstruction of the remaining images a lot if the denominators of the remaining rationals are small multiples of d (or vice versa) as is often the case. This option should always be used.

Examples

m13

m:=13

(1)

u12modm

u:=7

(2)

iratreconu&comma;m

12

(3)

iratreconu&comma;m&comma;2&comma;2

12

(4)

u13modm

u:=9

(5)

iratreconu&comma;m

FAIL

(6)

iratreconu&comma;m&comma;maxquo

FAIL

(7)

iratreconu&comma;m&comma;maxquo&comma;1

13

(8)

U0&comma;1&comma;2&comma;3&comma;4&comma;5&comma;6&comma;7&comma;8&comma;9&comma;10&comma;11&comma;12

U:=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

(9)

mapiratrecon&comma;U&comma;m

0&comma;1&comma;2&comma;FAIL&comma;FAIL&comma;FAIL&comma;12&comma;12&comma;FAIL&comma;FAIL&comma;FAIL&comma;2&comma;1

(10)

mapiratrecon&comma;U&comma;m&comma;2&comma;3

0&comma;1&comma;2&comma;FAIL&comma;13&comma;23&comma;12&comma;12&comma;23&comma;13&comma;FAIL&comma;2&comma;1

(11)

mapiratrecon&comma;U&comma;m&comma;3&comma;2

0&comma;1&comma;2&comma;3&comma;FAIL&comma;32&comma;12&comma;12&comma;32&comma;FAIL&comma;3&comma;2&comma;1

(12)

m19

m:=19

(13)

a1x223modm

a:=10x&plus;12

(14)

iratrecona&comma;m

12x23

(15)

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.

m8997101103

m:=89809099

(16)

f1234567891&plus;1x987654321&plus;97531y8642

f:=1234567891&plus;1987654321x&plus;975318642y

(17)

forpin107&comma;109&comma;113&comma;127&comma;131&comma;139&comma;151dommp&semi;ufmodm&semi;printp&comma;iratreconu&comma;m&comma;iratreconu&comma;m&comma;maxquoend do&colon;

107&comma;FAIL&comma;FAIL

109&comma;FAIL&comma;FAIL

113&comma;1076517573928&plus;975318642y22769726358627x&comma;FAIL

127&comma;FAIL&comma;1234567891&plus;1987654321x&plus;975318642y

131&comma;FAIL&comma;1234567891&plus;1987654321x&plus;975318642y

139&comma;1234567891&plus;1987654321x&plus;975318642y&comma;1234567891&plus;1987654321x&plus;975318642y

151&comma;1234567891&plus;1987654321x&plus;975318642y&comma;1234567891&plus;1987654321x&plus;975318642y

(18)

As mentioned, N,D not satisfying 2ND<m may be used, but a solution, if returned, is not necessarily unique.

iratrecon9&comma;13&comma;3&comma;3

13

(19)

iratrecon9&comma;13&comma;4&comma;4

4

(20)

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.

vVector1234541&comma;345782&comma;457123

v:=1234541345782457123

(21)

m4632746309

m:=2145357043

(22)

uvmodm

u:=57558389820145425472075589338

(23)

iratreconu&comma;m&comma;scaled

157173784345782457123

(24)

References

  

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.

See Also

map

mod

ratrecon

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam