多项式二元扩展欧几里得算法

Question

多项式二元扩展欧几里得算法

algorithmpolynomial-mathgreatest-common-divisorboolean-polynomials

3

存在一种二进制最大公约数算法，用于求一个数字的最大公约数。通常情况下，最大公约数可以扩展到扩展欧几里得算法，可以帮助找到一个域中的乘法逆元。

我正在使用表示多项式的二进制数字。例如，比特串1101表示x^3 + x^2 + 1。我需要计算模一个已知大质数p的x^p - 1多项式的模反元素。然而，我需要在常数时间内执行此操作（这意味着运行时间不应取决于我要求倒数的数字）。我知道如何使二进制最大公约数的运行时间保持不变，并且我知道如何实现用于计算乘法逆元的多项式XGCD。但是我不知道是否存在二进制多项式的等效最大公约数（以及相应的XGCD）。

- Sebastian

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user58697 · Accepted Answer

是的，有。在任何存在最小质数的环中，"二进制" GCD 都可以工作。对于整数，最小质数是 2，因此被称为二进制。对于多项式而言，最小质数是 x。该算法遵循相同的思路：通过减去多项式以消除高次项中的自由项，将最大可能的 x 幂因式分解，并继续进行，直到减法的结果变为零。