摘要 |
In one exemplary embodiment of the invention, a method for computing a resultant and a free term of a scaled inverse of a first polynomial v(x) modulo a second polynomial fn(x), including: receiving the first polynomial v(x) modulo the second polynomial fn(x), where the second polynomial is of a form fn(x)=xn±1, where n=2k and k is an integer greater than 0; computing lowest two coefficients of a third polynomial g(z) that is a function of the first polynomial and the second polynomial, where g(z)&Pgr;i=0n−1(v(&rgr;i)−z), where &rgr;0, &rgr;1, . . . , &rgr;n−1 are roots of the second polynomial fn(x) over a field; outputting the lowest coefficient of g(z) as the resultant; and outputting the second lowest coefficient of g(z) divided by n as the free teen of the scaled inverse of the first polynomial v(x) modulo the second polynomial fn(x).
|