CODEWITHSUNDEEP
algorithmpolynomial-mathgreatest-common-divisorboolean-polynomials
Sebastian
Sebastian

Reputation: 313

Binary XGCD for polynomials

There exists a binary GCD algorithm for finding the greatest common divisor of a number. In general, the GCD can be extended to the XGCD, which can help find a multiplicative inverse in a field.

I am working with binary numbers that represent a polynomial. For example, the bitstring 1101 represents x^3 + x^2 + 1. I need to compute the modular inverse of a random polynomial modulo x^p - 1 for some large known prime p. However, I need to do it in constant time (meaning that the runtime should not depend on the number I am inverting). I know how to make the binary GCD constant time and I know how to implement the XGCD for polynomials in order to compute multiplicative inverses. What I don't know is if there exists a binary GCD equivalent (with corresponding XGCD) for (binary) polynomials?

Upvotes: 3

Views: 763

Answers (1)

user58697
user58697

Reputation: 7923

Yes there is. The "binary" GCD works in any ring where the smallest prime exists. For integers it is 2, hence the name binary. For polynomials, it is x. The algorithm follows the same idea: subtract polynomials to eliminate a free term in one of higher degree, factor out the highest possible power of x, and keep going until the result of subtraction becomes zero.

Upvotes: 2

Related Questions