On the Relation Between Matrices and the Greatest Common Divisor of Polynomials

摘要

Following the Barnett's approach to gcd(a(x),b(x)) based on the use of companion matrix we develop an extended algorithm that gives effectively d(x), u(x), v(x), a_1(x) and b_1(x), where a_1(x) = a(x)/d(x),b_1(x) = b(x)/d(x) and d(x) = u(x)a(x) + v(x)b(x). The algorithm is suitable for parallel realization on GPU, FPGA, and smart cards.