This routine reconstructs a rational function $\frac{n}{d}$ from its image $u\mathbf{mod}m$ where u and m are polynomials in $F_x$, and $F$ is a field of characteristic p.

Given $u\mathbf{mod}m$ and non-negative integers N and D, if the call Ratrecon(u,m,x,N,D) mod p succeeds then the output is a rational function n/d in x such that

Otherwise Ratrecon returns FAIL indicating that no such polynomials n and d exist.  The reconstruction is unique up to multiplication by a constant in $F$ if the following condition holds.

N + D < degree(m,x)

If the optional parameters N and D are not specified then they are determined by the degree of m. They are assigned the largest possible values satisfying the above constraint such that N=D or N-D=1.

If the optional parameters n and d are specified then Ratrecon returns either true or false.  If rational reconstruction succeeds then true is returned and these parameters are assigned the numerator and denominator separately, otherwise false is returned and these parameters are not changed.

The special case of $m=x^k$ corresponds to computing the (N, D) Pade approximate to the series u of order $\mathrm{O}\left(x^k\right)$ .

If the first input u is a polynomial in variables other than x then Ratrecon is applied to the coefficients of the polynomial in those variables.  See the last example in the Examples section.

For the special case of $N=0$, the polynomial $\frac{d}{n}$ is the inverse of u in $\frac{F_x}{m}$ provided u and m are relatively prime.

$u≔3+5x+7x^2+11x^3+13x^4$

$u≔13x^4+11x^3+7x^2+5x+3$

$m≔x^5$

$m≔x^5$

$p≔97$

$p≔97$

$r≔\mathrm{Ratrecon}\left(u\&comma;m\&comma;x\right)\mathbf{mod}p$

$r≔\frac{19x^2+56x+77}{x^2+19x+58}$

$\mathrm{Ratrecon}\left(u\&comma;m\&comma;x\&comma;2\&comma;2\right)\mathbf{mod}p$

$\frac{19x^2+56x+77}{x^2+19x+58}$

$\mathrm{Ratrecon}\left(u\&comma;m\&comma;x\&comma;1\&comma;3\right)\mathbf{mod}p$

$\frac{27x+52}{x^3+43x^2+34x+82}$

$\mathrm{Ratrecon}\left(u\&comma;m\&comma;x\&comma;1\&comma;1\right)\mathbf{mod}p$

$\mathrm{FAIL}$

$\mathrm{Ratrecon}\left(u\&comma;m\&comma;x\&comma;2\&comma;2\&comma;'n'\&comma;'d'\right)\mathbf{mod}p$

$\mathrm{true}$

$n,d$

$19x^2+56x+77,x^2+19x+58$

$\mathrm{alias}\left(\mathrm{\alpha }=\mathrm{RootOf}\left(x^2+5\right)\right)$

$\mathrm{\alpha }$

$u≔5+7\mathrm{\alpha }+\left(11+13\mathrm{\alpha }\right)x+\left(17+19\mathrm{\alpha }\right)x^2$

$u≔5+7\mathrm{\alpha }+\left(11+13\mathrm{\alpha }\right)x+\left(17+19\mathrm{\alpha }\right)x^2$

$r≔\mathrm{Ratrecon}\left(u\&comma;x^3\&comma;x\right)\mathbf{mod}97$

$r≔\frac{2x\mathrm{\alpha }+3\mathrm{\alpha }+71x+46}{x+10\mathrm{\alpha }+21}$

$\mathrm{evala}\left(\mathrm{series}\left(r\&comma;x\&comma;3\right)\right)\mathbf{mod}97$

$5+7\mathrm{\alpha }+\left(11+13\mathrm{\alpha }\right)x+\left(17+19\mathrm{\alpha }\right)x^2+O\left(x^3\right)$

$\mathrm{`mod`}≔\mathrm{mods}\&colon;$

$u≔x^3+\left(6t^3-3t-5\right)x^2+\left(4t^3+6t^2+5t-4\right)x+\left(t-1\right)$

$u≔x^3+\left(6t^3-3t-5\right)x^2+\left(4t^3+6t^2+5t-4\right)x+t-1$

$m≔\left(t-2\right)\left(t-3\right)\left(t-4\right)\left(t-5\right)$

$m≔\left(t-2\right)\left(t-3\right)\left(t-4\right)\left(t-5\right)$

$p≔13$

$p≔13$

$\mathrm{Ratrecon}\left(u\&comma;m\&comma;t\&comma;1\&comma;2\right)\mathbf{mod}p$

$t-1-\frac{t{x}^2}{t-1}+x^3+\frac{2tx}{t^2-1}$