Rational number reconstruction
This functionality does not run in MATLAB.
numlib::reconstructRational(a
,n
)
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
. It returns FAIL
if
such p,q
do not exist.
numlib::reconstructRational(a,n)
returns p,q
by
solving
.
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)
.
If several pairs p,q
satisfy these conditions,
then their ratios p/q
are the same. In such case, numlib::reconstructRational
returns
the smallest of these pairs.
Solve this linear congruence: .
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)
Rational number reconstruction is mostly used as the last step of a modular algorithm. For example, find the greatest common divisors 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]):
Typically, you can use gcd
for
this task. However, suppose you know that the greatest common divisor
has small coefficients with numerator and denominator both smaller
than 10. Then you 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)
gcd(f,g)

An integer 

A positive integer 
Sequence consisting of an integer and a positive integer, or FAIL
[1] Davenport, J. H. , Y.Siret, and E.Tournier "Computer Algebra: Systems and Algorithms for Algebraic Computation". Academic Press Inc, 1988, p.142