AngouriMath

Navigation

Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug ~~Donate~~ Contacts

← Back to list of members

LiftPair(AngouriMath.Functions.IntegerPolynomial,AngouriMath.Functions.PrimeFieldPolynomial,AngouriMath.Functions.PrimeFieldPolynomial,System.Int64,PeterO.Numbers.EInteger,AngouriMath.Functions.IntegerPolynomial@,AngouriMath.Functions.IntegerPolynomial@)

Method (no overloads)

Summary

Lifts poly = left * right from modulo prime to modulo
modulus, one power at a time.

Remarks

Writing the next pair as A + m*alpha and B + m*beta and asking that
the product match one power further leaves alpha*B + beta*A = e modulo the
prime, where e is the error so far divided by m. The Bezout pair for
A and B modulo the prime solves that immediately, and reducing
alpha below the degree of A — pushing the quotient into beta —
is what keeps both sides at the degree they started with, so that the product stays
the degree of the polynomial being factored. Knuth, TAOCP vol. 2, §4.6.2,
algorithm H.
Each round checks that the product really does agree with the input to the power
just reached, and declines if it does not. The Bezout pair is computed once, from
the factors modulo the prime, and stays correct because neither factor changes
modulo the prime as it is lifted.

AngouriMath

Table of contents

AngouriMath