A Probabilistic Algorithm of Computing the Polynomial Greatest Common Divisor with Smaller Factors
YangZhang, Xin Qian, Qidi You, Xuan Zhou, Xiyong Zhang and Yang Wang, Space star technology co., LTD, China & State Key Laboratory of Space-Ground Integrated Information Technology, China
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.
Keywords: Euclidean Algorithm, extended Euclidean Algorithm, Subresultant Algorithm, Primitive Remainder Sequence, Ideal Lattice.