存在一种二进制最大公约数算法,用于求一个数字的最大公约数。通常情况下,最大公约数可以扩展到扩展欧几里得算法,可以帮助找到一个域中的乘法逆元。
我正在使用表示多项式的二进制数字。例如,比特串1101
表示x^3 + x^2 + 1。我需要计算模一个已知大质数p的x^p - 1多项式的模反元素。然而,我需要在常数时间内执行此操作(这意味着运行时间不应取决于我要求倒数的数字)。我知道如何使二进制最大公约数的运行时间保持不变,并且我知道如何实现用于计算乘法逆元的多项式XGCD。但是我不知道是否存在二进制多项式的等效最大公约数(以及相应的XGCD)。