Documentation Center

  • Trial Software
  • Product Updates

numlib::reconstructRational

Reconstruct a rational number from its image modulo N

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

numlib::reconstructRational(a, n)

Description

numlib::reconstructRational(a, n) returns two integers p, q of absolute value smaller than sqrt(n/2) with p congruent to a*q modulo n, or FAIL if such p, q do not exist.

numlib::reconstructRational(a, n) returns p, q solving . However, p/q mod n equals a only if p and q are relatively prime.

The solution p, q satisfies the following conditions: p is strictly between -sqrt(n/2) and sqrt(n/2), q is strictly between 0 and sqrt(n/2).

Several pairs p, q satisfying these conditions may exist, in which case their ratios p/q are all the same; then the smallest of them is returned.

Examples

Example 1

We want to solve :

numlib::reconstructRational(7, 12)

Modulo 98, the same congruence has no small solution. The solution p=7, q=1 is not small enough as 7 is not smaller than sqrt(98/2) but just equal.

numlib::reconstructRational(7, 98)

Example 2

Rational number reconstruction is mostly used as the last step of a modular algorithm. Let us compute the gcd of the following polynomials:

f:=  poly(x^5 + 22/35*x^3 + 3/8*x^2 + 3/35*x + 9/56, [x]):
g:= poly(x^5 + 2/5*x^4 + 22/35*x^3 + 153/280*x^2 + 3/35*x + 9/56,
    [x]):

Of course, the function gcd is able to do this. However, suppose we know that for some reason that the gcd has small coefficients with numerator and denominator both smaller than 10. Then we can use a modular algorithm with a smaller modulus than gcd would do: to be able to reconstruct these from their residue class modulo n, it is sufficient that , e.g., n=211.

gcd(poly(f, IntMod(211)), poly(g, IntMod(211)))

Rational number reconstruction shows that the constant coefficient must be 3/7:

numlib::reconstructRational(-90, 211)

This is true indeed:

gcd(f,g)

Parameters

a

Integer

n

A positive integer

Return Values

Sequence consisting of an integer and a positive integer; or FAIL

References

[1] Davenport, J. H. , Y.Siret, and E.Tournier "Computer Algebra: Systems and Algorithms for Algebraic Computation". Academic Press Inc, 1988, p.142

The algorithm may be found in Davenport/Siret/Tournier, Computer algebra, p. 142.

See Also

MuPAD Functions

Was this topic helpful?