## Documentation Center |

Reconstruct a rational number from its image modulo N

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`, 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.

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)

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)

[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.

Was this topic helpful?