RatReconstructPoly

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