RationalReconstruction

The small fraction $n/d$ whose image in $\mathbb{Z}/m$ is $a$ — the inverse of reading $n/d$ as $n \cdot d^{-1} \bmod m$.

RationalReconstruction(a, m)the $n/d$ with $n \equiv a d \pmod m$ and $|n|, d \le \sqrt{(m-1)/2}$, when there is one

SageMathrational_reconstruction(a, m)

RationalReconstruction(a, m, N, D)with explicit bounds $|n| \le N$, $0 < d \le D$, and over a list of residues

Typed signatures

Type	Package	Applies
(integer, integer) -> rational	compute-engine	always
(integer, integer, integer?, integer?) -> rational	number-theoryreplaces compute-engine	always

Domain: Number theory

Details

• Every residue is the image of infinitely many fractions, but at most one with $2ND < m$ — so under the default balanced bounds the answer, when it exists, is unique.
• Wang's algorithm: the extended Euclidean algorithm on $(m, a)$, stopped at the first remainder $\le N$; the remainder and its cofactor are $n$ and $d$.
• Not a Wolfram built-in; the name follows SageMath's rational_reconstruction (Maple: iratrecon).
• Unevaluated when no fraction within the bounds maps to $a$. Threads over lists.

Examples

Basic #

$2 \cdot 6 = 12 \equiv 1 \pmod{11}$

live ↗

In$\mathrm{RationalReconstruction}(6, 11)$Out$\frac{1}{2}$

a round trip through $\mathbb{Z}/1000003$

live ↗

In$\mathrm{RationalReconstruction}(\mathrm{PowerMod}(\frac{22}{7}, 1, 1\,000\,003), 1\,000\,003)$Out$\frac{22}{7}$

Scope #

explicit bounds: denominators of 1 only

live ↗

In$\mathrm{RationalReconstruction}(5, 11, 5, 1)$Out$5$

live ↗

In$\mathrm{RationalReconstruction}(\bigl\lbrack6, 9, 10\bigr\rbrack, 11)$Out$\bigl\lbrack\frac{1}{2}, -2, -1\bigr\rbrack$

the harmonic number $H_{20}$, back from its image mod $2^{61} - 1$

live ↗

In$\mathrm{RationalReconstruction}(\mathrm{PowerMod}(\frac{55\,835\,135}{15\,519\,504}, 1, 2^{61}-1), 2^{61}-1)$Out$\frac{55\,835\,135}{15\,519\,504}$

Applications #

one word-size prime is not enough for $H_{20}$: $2ND < m$ needs $m$ past $1.7 \cdot 10^{15}$

live ↗

In$\mathrm{RationalReconstruction}(\mathrm{PowerMod}(\frac{55\,835\,135}{15\,519\,504}, 1, 1\,000\,000\,007), 1\,000\,000\,007)$Out$\mathrm{RationalReconstruction}(301\,316\,272, 1\,000\,000\,007)$

multi-modular arithmetic: glue two images with ChineseRemainder, and the product modulus is large enough

live ↗

In$\mathrm{RationalReconstruction}(\mathrm{ChineseRemainder}(\bigl\lbrack\mathrm{PowerMod}(55\,835\,135/15\,519\,504, 1, 1\,000\,000\,007), \mathrm{PowerMod}(55\,835\,135/15\,519\,504, 1, 1\,000\,000\,009)\bigr\rbrack, \bigl\lbrack1\,000\,000\,007, 1\,000\,000\,009\bigr\rbrack), 1\,000\,000\,007×1\,000\,000\,009)$Out$\frac{55\,835\,135}{15\,519\,504}$

Possible issues #

mod 11 the bounds are $|n|, d \le 2$, and no such fraction is $\equiv 3$

live ↗

In$\mathrm{RationalReconstruction}(3, 11)$Out$\mathrm{RationalReconstruction}(3, 11)$

About

Examples	8
Checked against	SageMath 3 agree3 error
Crosswalk	SageMath

Implementation

mappedsagepackages/oracle/src/mappings.ts

See also: PowerModList, ChineseRemainder, Rationalize, ContinuedFraction