up previous next
 RatReconstructPoly    --    Rational reconstruction of polynomial coefficents

 Syntax
 `RatReconstructPoly(f1: RINGELEM, M1: INT): RINGELEM`

 Description
This function attempts to reconstruct the rational coefficents of a polynomial f from a modular image f mod M . The algorithm is fault-tolerant: it will succeed provided that the coefficients in f are correct modulo a sufficiently large factor of M .

NOTE: so that the heuristic can work, the modulus must be larger than strictly necessary; indeed, reconstruction always fails if M is small.

 Example
 ```/**/ use QQ[x,y]; /**/ RatReconstructPoly(10923689802589*x^2 +8192767351939*y, 32771069407757); (10/3)*x^2 +(-1/4)*y -- input comes from CTR computation: /**/ RingElem(NewPolyRing(NewZZmod(32003),"x,y"), "(10/3)*x^2 +(-1/4)*y"); 10671*x^2 -8001*y /**/ RingElem(NewPolyRing(NewZZmod(31991),"x,y"), "(10/3)*x^2 +(-1/4)*y"); 10667*x^2 -7998*y /**/ RingElem(NewPolyRing(NewZZmod(32009),"x,y"), "(10/3)*x^2 +(-1/4)*y"); 10673*x^2 +8002*y /**/ CRTPoly(10671*x^2 -8001*y, 32003, 10667*x^2 -7998*y, 31991); record[modulus := 1023807973, residue := -341269321*x^2 +255951993*y] /**/ CRTPoly(It.residue, It.modulus, 10673*x^2 +8002*y, 32009); record[modulus := 32771069407757, residue := 10923689802589*x^2 +8192767351939*y] /**/ RatReconstructPoly(It.residue, It.modulus); (10/3)*x^2 +(-1/4)*y ```

 See Also