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

/**/ RatReconstructPoly(-341269321*x^2 +255951993*y, 1023807973);
(10/3)*x^2 +(-1/4)*y

/**/ ReadExpr(NewPolyRing(NewRingFp(32003),"x,y"), "(10/3)*x^2 +(-1/4)*y");
10671*x^2 -8001*y
/**/ ReadExpr(NewPolyRing(NewRingFp(31991),"x,y"), "(10/3)*x^2 +(-1/4)*y");
10667*x^2 -7998*y

/**/ CRTPoly(10671*x^2 -8001*y, 32003,    10667*x^2 -7998*y, 31991);
record[modulus := 1023807973, residue := -341269321*x^2 +255951993*y]

See Also