Let G be the greatest common divisor (GCD) of two polynomials A,B in Z[x,y,z] where x is the main variable. Suppose G = (4y^2+2z)x^2 + (5y^2+3z). Because G is not monic in x the sparse modular GCD algorithm of Richard Zippel cannot be applied directly as one is unable to scale the univariate images of G in x consistently. We call this the "normalization problem". It can be solved in a number of ways. The approach taken by Paul Wang is to factor the leading coefficient L(y,z) of one of the input polynomials over Z and determine which factors of L belong with G. If A or B is sparse then one can usually select a main variable and leading coefficient that is easy to factor. If A and B are not sparse, the factorization could be expensive.

We present two new sparse modular GCD algorithms which do not require any factorization. The first algorithm is a modification of Zippel's algorithm where the scaling factors are treated as unknowns to be solved for. This leads to a structured coupled linear system for which an efficient solution is still possible. The second algorithm reconstructs the monic GCD x^2 + (10y^2+6z)/(2y^2+z) from monic univariate images using a sparse, variable at a time, rational function interpolation algorithm. We present an initial run-time comparison of a Maple implementation of the two methods on three classes of GCD problems.