A Probabilistic Algorithm of Computing the Polynomial Greatest Common Divisor with Smaller Factors

Abstract: In the earlier work, subresultant algorithm was proposed to decrease the coefficient growth in the Euclidean algorithm of polynomials. However, the output polynomial remainders may have a small factor which can be removed to satisfy our needs. Then later, an improved subresultant algorithm was given by representing the subresultant algorithm in another way, where we add a variant called 𝜏 to express the small factor. There was a way to compute the variant proposed by Brown, who worked at IBM. Nevertheless, the way failed to determine each𝜏 correctly. In this paper, we will give a probabilistic algorithm to determine the variant 𝜏 correctly in most cases by adding a few steps instead of computing 𝑡 𝑥 when given 𝑓 𝑥 and𝑔 𝑥 ∈ ℤ 𝑥 , where 𝑡 𝑥 satisfies that 𝑠 𝑥 𝑓 𝑥 + 𝑡 𝑥 𝑔 𝑥 = 𝑟 𝑥 , here 𝑡 𝑥 , 𝑠 𝑥 ∈ ℤ 𝑥 .Also , we made experiments on the correctness and efficiency of our algorithm, which has obvious advantage compared with the previous fastest algorithm.