Current Issue

November 2022 - Volume 11, Number 1/2/3/4

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

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.

Keywords: Euclidean Algorithm, extended Euclidean Algorithm, Subresultant Algorithm, Primitive Remainder Sequence, Ideal Lattice.

Full Text