3

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?

Sebastian
  • 313
  • 1
  • 15

1 Answers1

2

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.

user58697
  • 7,808
  • 1
  • 14
  • 28
  • That's cool, the factor _x_ is the same as the value 2 in the binary representation, which means that multiplication/division by _x_ is just bitshifting, just as it is when multiplying/dividing by 2. Also, "odd"/"even" can be determined by inspecting just the last bit. Also, addition is equal to subtraction (xor) and has no carries. All in all, I'd say this is going to be a fast algorithm. – Sebastian Aug 11 '16 at 18:44