| 摘要 |
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 ) ⁢ = def ⁢ ∏ i = 0 n - 1 ⁢ ⁢ ( v ⁡ ( rho i ) - z ) , where rho0, rho1, . . . , rhon-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 term of the scaled inverse of the first polynomial v(x) modulo the second polynomial fn(x).
|
