Resultants for Univariate Polynomials7/14/2008, 10.45-12.15Manfred MinimairE-mail: manfred@minimair.orgDepartment of Mathematics and Computer ScienceSeton Hall University, South Orange, New Jersey, USAImportance of resultantsFundamental for solving systems of polynomial equationsMany applications where polynomial equations arise:
e.g. computer graphics, robotics, computational chemistry, ...Univariate resultantsProblem statementBasic casesSylvester constructionBezout constructionTypical usesReferences: any textbook on computer algebraProblem statementInput: polynomials f and g in variable xOutput: a number r, the resultant of f and g, that is zero if and only if f and g have a common rootmore precisely:Vanishing Theoremf and g have a common root or the leading coefficients of f and g both vanish iff thre resultant r vanishes.The resultant is an irreducible polynomial in the coefficients of f and g.ExamplesQyQ+SSJmRzYiLUklc29ydEclKnByb3RlY3RlZEc2JC1JKXJhbmRwb2x5RzYkRihJKF9zeXNsaWJHRiU2JEkieEdGJS9JJ2RlZ3JlZUdGKCIiI0YvIiIiQyQ+SSJnRzYiLUklc29ydEclKnByb3RlY3RlZEc2JC1JKXJhbmRwb2x5RzYkRihJKF9zeXNsaWJHRiU2JEkieEdGJS9JJ2RlZ3JlZUdGKCIiJEYvIiIiQyQtSSpyZXN1bHRhbnRHNiI2JUkiZkdGJUkiZ0dGJUkieEdGJSIiIg==Resultant does not vanish. Therefore f and g do not have a common rootQyQ+SSJmRzYiLUklc29ydEclKnByb3RlY3RlZEc2JC1JJ2V4cGFuZEdGKDYjKiYsJkkieEdGJSIiIkYwISIiRjAtSSlyYW5kcG9seUdGJTYkRi8vSSdkZWdyZWVHRihGMEYwRi9GMA==QyQ+SSJnRzYiLUklc29ydEclKnByb3RlY3RlZEc2JC1JJ2V4cGFuZEdGKDYjKiYsJkkieEdGJSIiIkYwISIiRjAtSSlyYW5kcG9seUc2JEYoSShfc3lzbGliR0YlNiRGLy9JJ2RlZ3JlZUdGKCIiI0YwRi9GMA==QyQtSSpyZXN1bHRhbnRHNiI2JUkiZkdGJUkiZ0dGJUkieEdGJSIiIg==QyQtSSV3aXRoRzYiNiNJKUdyb2VibmVyRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlIiIiQyQtSSZCYXNpc0c2IjYkNyRJImZHRiVJImdHRiUtSSVwbGV4R0YlNiNJInhHRiUiIiI=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnIndeed, f and g have the common root x = 1.LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnQyQ+SSJmRzYiLCgqJkkjYTJHRiUiIiIpSSJ4R0YlIiIjRilGKSomSSNhMUdGJUYpRitGKUYpSSNhMEdGJUYpRik=QyQ+SSJnRzYiLCoqJkkjYjNHRiUiIiIpSSJ4R0YlIiIkRilGKSomSSNiMkdGJUYpKUYrIiIjRilGKSomSSNiMUdGJUYpRitGKUYpSSNiMEdGJUYpRik=QyQ+SSJyRzYiLUkqcmVzdWx0YW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiVJImZHRiVJImdHRiVJInhHRiUiIiI=QyQ+SSNnYkc2Ii1JJkJhc2lzR0YlNiQ3JEkiZkdGJUkiZ0dGJS1JJXBsZXhHRiU2KkkieEdGJUkjYTJHRiVJI2ExR0YlSSNhMEdGJUkjYjNHRiVJI2IyR0YlSSNiMUdGJUkjYjBHRiUhIiI=QyQtSSVub3BzRyUqcHJvdGVjdGVkRzYjSSNnYkc2IiIiIg==QyQmSSNnYkc2IjYjIiIjIiIiQyQmSSNnYkc2IjYjIiIiRic=QyQtSShpcnJlZHVjRzYiNiNJInJHRiUiIiI=The resultant is an irreducible polynomial in the coefficients of f and g.QyQtSSVzdWJzRyUqcHJvdGVjdGVkRzYkNyQvSSNhMkc2IiIiIS9JI2IzR0YqRitJInJHRioiIiI=If the leading coefficients of f and g vanish then the resultant vanishes.Basic cases1 Resultant of two polynomials of degree 0By defintion,QyQtSSpyZXN1bHRhbnRHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2JUkjYTBHRihJI2IwR0YoSSJ4R0YoIiIiWhy? There is no single polynomial such that both a0 and b0 vanish.2 Resultant of two polynomials of degree 1QyQ+SSJmRzYiLCYqJkkjYTFHRiUiIiJJInhHRiVGKUYpSSNhMEdGJUYpRik=QyQ+SSJnRzYiLCYqJkkjYjFHRiUiIiJJInhHRiVGKUYpSSNiMEdGJUYpRik=QyQtSSZzb2x2ZUc2IjYkNyRJImZHRiVJImdHRiVJInhHRiUiIiI=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnWhat is the resultant of f and g?Idea: view f=0 and g=0 as two linear equationsQyQvLCYqJkkjYTFHNiIiIiJJInhHRidGKEYoKiZJI2EwR0YnRihJInpHRidGKEYoIiIhRig=QyQvLCYqJkkjYjFHNiIiIiJJInhHRidGKEYoKiZJI2IwR0YnRihJInpHRidGKEYoIiIhRig=where z = 1.There is a non-trivial solution (x,1) iffQyQvLCYqJkkjYjFHNiIiIiJJI2EwR0YnRighIiIqJkkjYjBHRidGKEkjYTFHRidGKEYoIiIhRig=The resultant is the determinant of the linear system:QyQtSSpyZXN1bHRhbnRHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2JUkiZkdGKEkiZ0dGKEkieEdGKCIiIg==Sylvester construtionIdea: linearize problemExample:QyQ+SSJmRzYiLCgqJkkjYTJHRiUiIiIpSSJ4R0YlIiIjRilGKSomSSNhMUdGJUYpRitGKUYpSSNhMEdGJUYpRik=QyQ+SSJnRzYiLCoqJkkjYjNHRiUiIiIpSSJ4R0YlIiIkRilGKSomSSNiMkdGJUYpKUYrIiIjRilGKSomSSNiMUdGJUYpRitGKUYpSSNiMEdGJUYpRik=Idea: maybe replace powers of x by new variables: x^3LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYsNihRImFGJy8lJXNpemVHUSMxMkYnRi8vJStmb3JlZ3JvdW5kR1ErWzAsMTYwLDgwXUYnLyUscGxhY2Vob2xkZXJHRjFGMg== = x3, x^2=x2, x1=x, x0=1f = a2 x2 + a1 x1 + a0 x0g = b3 x3 + b2 x2 + b1 x1 + b0 x0Consider sequence of equationsQyQqJilJInhHNiIiIiMiIiJJImZHRiZGKEYoQyQvLUkoY29sbGVjdEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYpSSJ4R0YpIiIjIiIiSSJmR0YpRi9GLSIiIUYvQyQvLUkoY29sbGVjdEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiZJInhHRikiIiJJImZHRilGLUYsIiIhRi0=QyQvSSJmRzYiIiIhIiIiQyQvLUkoY29sbGVjdEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiZJInhHRikiIiJJImdHRilGLUYsIiIhRi0=QyQvSSJnRzYiIiIhIiIiView as linear equations inQyQ3JyokKUkieEc2IiIiJSIiIiokKUYmIiIkRikqJClGJiIiI0YpRiZGKUYpCoefficient matrix is the Sylvester matrix:QyQtSSV3aXRoRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiNJLkxpbmVhckFsZ2VicmFHNiRGJ0YmISIiLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUkjbWlHRiQ2JVEuTGluZWFyQWxnZWJyYUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNjBRIzotRicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0Y9LyUpc3RyZXRjaHlHRj0vJSpzeW1tZXRyaWNHRj0vJShsYXJnZW9wR0Y9LyUubW92YWJsZWxpbWl0c0dGPS8lJ2FjY2VudEdGPS8lJWZvcm1HUSFGJy8lJ2xzcGFjZUdRJDBlbUYnLyUncnNwYWNlR0ZPLyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUYsNiVRMFN5bHZlc3Rlck1hdHJpeEYnRi9GMi1JKG1mZW5jZWRHRiQ2JC1GIzYnLUYsNiVRImZGJ0YvRjItRjY2MFEiLEYnRjlGOy9GP0YxRkBGQkZERkZGSC9GS1EmaW5maXhGJ0ZNL0ZRUTN2ZXJ5dGhpY2ttYXRoc3BhY2VGJ0ZSRlUtRiw2JVEiZ0YnRi9GMkZdby1GLDYlUSJ4RidGL0YyRjktRjY2MFEiO0YnRjlGO0Zgb0ZARkJGREZGRkhGYW9GTS9GUVEvdGhpY2ttYXRoc3BhY2VGJ0ZSRlU=If the linearized system has a non-trivial root then the determinant of the Sylvester matrix vanishes.Thus, define resultant to be the determinant of the Sylvester matrix. It can be shown that this definition satisfies the Vanishing Theorem.General algorithm for constructing the Sylvester matrix and the resultantInput:f polynomial of degree mg polynomial of degree nOutput:Sylvester matrix of f and g, and determinant of Sylvester matrix = resultant of f and gAlgorithm for Sylvester matrix:Construct matrix of size m+n.First block of n rows contains coefficients of f and second block of remaining m rows contains coefficients of g.The two blocks are constructed similarly. The first row contains the coefficients of f (or g) and the remaining entries are filled with zero. The subsequent rows are obtained from the previous row by adding a 0 in front and deleting a 0 at the end of the row. (See example above)Bezout constructionAlgorithm:Compute Bezout polynomial (f(x)*g(z)-f(z)*g(x))/(x-z)Construct the Bezout matrix which is the coefficient matrix of the Bezout polynomialResultant is the determinant of the Bezout matrix if f and g have the same degreeExampleQyQ+SSJmRzYiLCgqJkkjYTJHRiUiIiIpSSJ4R0YlIiIjRilGKSomSSNhMUdGJUYpRitGKUYpSSNhMEdGJUYpRik=QyQ+SSJnRzYiLCgqJkkjYjJHRiUiIiIpSSJ4R0YlIiIjRilGKSomSSNiMUdGJUYpRitGKUYpSSNiMEdGJUYpRik=QyQ+SSJuRzYiLUknbm9ybWFsRyUqcHJvdGVjdGVkRzYjKiYsJiomSSJmR0YlIiIiLUklc3Vic0dGKDYkL0kieEdGJUkiekdGJUkiZ0dGJUYuRi4qJi1GMDYkRjJGLUYuRjVGLiEiIkYuLCZGM0YuRjRGOUY5Ri4=QyQtSShjb2xsZWN0RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiVJIm5HRig3JEkieEdGKEkiekdGKEksZGlzdHJpYnV0ZWRHRigiIiI=LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2JVExQmV6b3V0UG9seW5vbWlhbEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNjBRIn5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUlZm9ybUdRIUYnLyUnbHNwYWNlR1EkMGVtRicvJSdyc3BhY2VHRk8vJShtaW5zaXplR1EiMUYnLyUobWF4c2l6ZUdRKWluZmluaXR5RictRjY2MFEqJmNvbG9uZXE7RidGOUY7Rj5GQEZCRkRGRkZIL0ZLUSZpbmZpeEYnL0ZOUS90aGlja21hdGhzcGFjZUYnL0ZRRmhuRlJGVUY1LUYsNiVRJXNvcnRGJ0YvRjItSShtZmVuY2VkR0YkNiQtRiM2Ji1GLDYlUShjb2xsZWN0RidGL0YyLUZebzYkLUYjNigtRiw2JUY6Ri9GMi1GXm82JC1GIzYjLUZebzYkLUYjNiMtSSZtZnJhY0dGJDYoLUYjNistRiw2JVEiZkYnRi9GMi1GNjYwUScmc2RvdDtGJ0Y5RjtGPkZARkJGREZGRkhGZW5GTUZQRlJGVS1GLDYlUSVzdWJzRidGL0YyLUZebzYkLUYjNictRiw2JVEieEYnRi9GMi1GNjYwUSI9RidGOUY7Rj5GQEZCRkRGRkZIRmVuRmduRmluRlJGVS1GLDYlUSJ6RidGL0YyLUY2NjBRIixGJ0Y5RjsvRj9GMUZARkJGREZGRkhGZW5GTS9GUVEzdmVyeXRoaWNrbWF0aHNwYWNlRidGUkZVLUYsNiVRImdGJ0YvRjJGOS1GNjYwUSomdW1pbnVzMDtGJ0Y5RjtGPkZARkJGREZGRkhGZW4vRk5RMG1lZGl1bW1hdGhzcGFjZUYnL0ZRRltzRlJGVUZecS1GXm82JC1GIzYnRmVxRmhxRltyRl5yRmhwRjlGW3FGZHItRiM2JUZlcUZnckZbci8lLmxpbmV0aGlja25lc3NHUSIxRicvJStkZW5vbWFsaWduR1EnY2VudGVyRicvJSludW1hbGlnbkdGaHMvJSliZXZlbGxlZEdGPUY5RjlGXnItRl5vNiYtRiM2JUZlcUZeckZbckY5LyUlb3BlbkdRIltGJy8lJmNsb3NlR1EiXUYnRl5yLUYsNiVRLGRpc3RyaWJ1dGVkRidGL0YyRjlGXnJGXXRGOS1GLDYlRkxGL0YyLUY2NjBRIjtGJ0Y5RjtGYXJGQEZCRkRGRkZIRmVuRk1GaW5GUkZVLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYrLUkjbWlHRiQ2JVEiTUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNjBRIn5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUlZm9ybUdRIUYnLyUnbHNwYWNlR1EkMGVtRicvJSdyc3BhY2VHRk8vJShtaW5zaXplR1EiMUYnLyUobWF4c2l6ZUdRKWluZmluaXR5RictRjY2MFEqJmNvbG9uZXE7RidGOUY7Rj5GQEZCRkRGRkZIL0ZLUSZpbmZpeEYnL0ZOUS90aGlja21hdGhzcGFjZUYnL0ZRRmhuRlJGVUY1LUYsNiVRLkxpbmVhckFsZ2VicmFGJ0YvRjItRjY2MFEjOi1GJ0Y5RjtGPkZARkJGREZGRkhGSkZNRlBGUkZVLUYsNiVRLUJlem91dE1hdHJpeEYnRi9GMi1JKG1mZW5jZWRHRiQ2JC1GIzYnLUYsNiVRImZGJ0YvRjItRjY2MFEiLEYnRjlGOy9GP0YxRkBGQkZERkZGSEZlbkZNL0ZRUTN2ZXJ5dGhpY2ttYXRoc3BhY2VGJ0ZSRlUtRiw2JVEiZ0YnRi9GMkZbcC1GLDYlUSJ4RidGL0YyRjktRjY2MFEiO0YnRjlGO0ZecEZARkJGREZGRkhGZW5GTUZpbkZSRlU=QyQtSSVzb3J0RyUqcHJvdGVjdGVkRzYkLUkoY29sbGVjdEc2JEYlSShfc3lzbGliRzYiNiUtSTBkZWxheURvdFByb2R1Y3RHNiRGJS9JK21vZHVsZW5hbWVHRitJLFR5cGVzZXR0aW5nR0YpNiQtRi42JC0mSSdWZWN0b3JHRik2I0kkcm93R0YrNiM3JCIiIkkieEdGK0kiTUdGKy0mRjg2I0knY29sdW1uR0YrNiM3JEkiekdGK0Y9NyRGPkZGSSxkaXN0cmlidXRlZEdGK0ZHRj0=QyQtX0kuTGluZWFyQWxnZWJyYUc2JEkoX3N5c2xpYkc2IiUqcHJvdGVjdGVkR0ksRGV0ZXJtaW5hbnRHRig2I0kiTUdGKCIiIg==QyQtSSpyZXN1bHRhbnRHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2JUkiZkdGKEkiZ0dGKEkieEdGKCIiIg==Case of f and g with different degrees:Determinant of Bezout matrix is a multiple of the resultant. Bezout matrix can be adjusted such that the determinant is the resultant.Typical uses1 Determine parameters such that two polynomials have a common rootExampleQyQ+SSJmRzYiLCgqJClJInhHRiUiIiMiIiJGKyomSSJwR0YlRitGKUYrRitGK0YrRis=QyQ+SSJnRzYiLCoqJClJInhHRiUiIiQiIiJGKyomSSJwR0YlRispRikiIiNGK0YrKiYiIiZGK0YtRitGK0YrISIiRis=QyQ+SSJyRzYiLUklc29ydEclKnByb3RlY3RlZEc2JC1JKnJlc3VsdGFudEc2JEYoSShfc3lzbGliR0YlNiVJImZHRiVJImdHRiVJInhHRiVJInBHRiUiIiI=QyQ+NiRJI3AxRzYiSSNwMkdGJi1JJnNvbHZlRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YmNiMvSSJyR0YmIiIhIiIiFor p=p1 or p=p2 the polynomials f and g have a common root.E.g.QyQ+SSNmMUc2Ii1JJXN1YnNHJSpwcm90ZWN0ZWRHNiQvSSJwR0YlSSNwMUdGJUkiZkdGJSIiIg==QyQ+SSNnMUc2Ii1JJXN1YnNHJSpwcm90ZWN0ZWRHNiQvSSJwR0YlSSNwMUdGJUkiZ0dGJSIiIg==QyQtSSZzb2x2ZUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYjNyQvSSNmMUdGKCIiIS9JI2cxR0YoRi0iIiI=2 Eliminate variables for solving systems of equationsExampleQyQ+SSJmRzYiLUklc29ydEclKnByb3RlY3RlZEc2JC1JKXJhbmRwb2x5RzYkRihJKF9zeXNsaWJHRiU2JDckSSJ4R0YlSSJ5R0YlL0knZGVncmVlR0YoIiIjRi8iIiI=QyQ+SSJnRzYiLUklc29ydEclKnByb3RlY3RlZEc2JC1JKGNvbGxlY3RHNiRGKEkoX3N5c2xpYkdGJTYlLUkiKkdGKDYkLUkpcmFuZHBvbHlHRiw2JDckSSJ4R0YlSSJ5R0YlL0knZGVncmVlR0YoIiIiRjJGNUksZGlzdHJpYnV0ZWRHRiVGNUY6(Note: "simple" g, product of two degree 1 polynomials, is used here in order to get "nice" roots for this example.)Eliminate x:QyQ+SSJyRzYiLUkqcmVzdWx0YW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiVJImZHRiVJImdHRiVJInhHRiUiIiI=Solve r = 0 for y:QyQ+NiZJI3kxRzYiSSN5MkdGJkkjeTNHRiZJI3k0R0YmLUkmc29sdmVHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiY2JC9JInJHRiYiIiFJInlHRiYiIiI=Plug y into f or g and solve for x:QyQtSSZzb2x2ZUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYjLUklc3Vic0dGJjYkL0kieUdGKEkjeTFHRigvSSJmR0YoIiIhIiIiQyQtSSZzb2x2ZUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYjLUklc3Vic0dGJjYkL0kieUdGKEkjeTJHRigvSSJmR0YoIiIhIiIiQyQtSSZzb2x2ZUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYjLUklc3Vic0dGJjYkL0kieUdGKEkjeTNHRigvSSJmR0YoIiIhIiIiQyQtSSZzb2x2ZUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYjLUklc3Vic0dGJjYkL0kieUdGKEkjeTRHRigvSSJmR0YoIiIhIiIiFinally check that all the computed roots of f are also roots of g.LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn