Scholarlink

Let \({\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)}\) be an algebraic number field. In 2023, Ansari and Monagan designed a modular algorithm to compute the monic gcd g of two polynomials \(f_1\) and \(f_2\) in \({\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)}[x_1,\ldots ,x_k]\) . The algorithm computes g modulo primes and uses interpolation to recover \(x_2,x_3,\dots ,x_k\) in g. However, the algorithm may fail in certain cases, for instance, when encountering a zero divisor. In this paper, we present a refined classification of failure cases for this algorithm and provide a detailed analysis of their probabilities.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Failure Probability Analysis of a Modular Algorithm to Compute the Monic GCD of Multivariate Polynomials over Algebraic Number Fields \({\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)}\)

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Mahsa Ansari,
  • Michael Monagan

摘要

Let \({\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)}\) be an algebraic number field. In 2023, Ansari and Monagan designed a modular algorithm to compute the monic gcd g of two polynomials \(f_1\) and \(f_2\) in \({\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)}[x_1,\ldots ,x_k]\) . The algorithm computes g modulo primes and uses interpolation to recover \(x_2,x_3,\dots ,x_k\) in g. However, the algorithm may fail in certain cases, for instance, when encountering a zero divisor. In this paper, we present a refined classification of failure cases for this algorithm and provide a detailed analysis of their probabilities.