From the equation bounding *r*(*n*)*g*(*n*) we can derive

or

This bound is rather tight. The first use of this bound is to estimate

The second use of the upper bound on *d*_{g} is more interesting.
So far we have tried to lift *g*(*x*).
But it is equally possible to lift one of the cofactors,
that is *c*_{a}(*x*) or *c*_{b}(*x*).
By knowing the degrees of *a*(*x*), *b*(*x*) and an estimate of
the degree of *g*(*x*) we can decide to lift the polynomial with
the lowest degree (which in practice will the least expensive
to lift).

# Cofactor lifting n := any_choice; an := a(n); ca := genpoly( an / igcd( an, b(n) ), n, x ); if divide( a(x), ca, 'g' ) and divide( b, g ) then # success else g := FAIL fi;

The cofactor lifting has a significant advantage on the
previous lifting. The above procedure, if successful,
produces the correct result for any value of *n*. So we
can choose *n* as small as we wish.
The proof of correctness is based on the fact that a
poor choice of *n* or *r*(*n*) may lift a *c*_{a}(*x*) of lower
degree, which means that *g*(*x*) will be of higher
degree. Hence this will never pass the test.

If *r*(*n*) is not 1, then the above procedure will not work,
i.e. it will always fail.
This can be improved by finding the common fixed divisor
of both polynomials as shown above. It is also possible
to allow for some extra spurious factors in *r*(*n*) and multiply
*a*(*n*) by small integers.

The combination of lifting the gcd or one of its cofactors
is quite complementary.
It happens for unbalanced problems that either the gcd is
large (large degree and large coefficients) or the cofactor
is large.
The lifting of non-large polynomials is more efficient
(will not need to increase *n*).

The main paper on this subject is [1]. The original proofs and the actual algorithm implemented in Maple differ from the one presented here.