Multiplying two polynomials

Question

This is a question asked in some interview questions.

Given three polynomials f(x), g(x), h(x) where the co-efficient are binary. Give [f(x)*g(x)] mod h(x) [All operation in binary co-efficient]

Polynomials are given in this format… x3 + x + 1 is given as “1011”. Write a program char* multmod (char *f, char *g, char *h) that will output polynomial… (f*g) mod h

What could be the approach? can we do something at bit level?

Answer 1

Motivation

Binary coefficients here means that the coefficients are modulo 2, in the field Z_2, or just take on the values 0 and 1 and operate like bits. It does not mean the coefficients are arbitrary integers represented in base two. They are binary (take on exactly two values), as opposed to simply being expressed in a binary numeral system.

With this firmly in mind, this question is fairly easy to answer, and yes, bitwise operations of XOR and (left) shifts will suffice. Though not required to answer this question, this question is motivated by cryptography. It demonstrates the link between some bitwise operations commonly used in hashing and some encryption schemes and abstract algebra, so that results about polynomials over finite fields can be leveraged in cryptanalysis. Taking the product modulo another polynomial is to prevent the degree of the result from growing past a certain limit. Operations on machine registers do this naturally as overflow.

Addition

First let’s talk about addition. As the coefficients are modulo 2, adding x + x = 2x = 0x = 0 since 2 mod 2 = 0. So, whenever there is two of the same term, they cancel, and when there is only one it persists. This is the same behavior as XOR. For example, adding (x^4 + x^2 + 1) + (x^3 + x^2):

(1x^4+0x^3+1x^2+0x^1+1x^0)+(0x^4+1x^3+1x^2+0x^1+0x^0) = (1x^4+1x^3+0x^2+0x^1+1x^0) 

or, using the compact coefficient only notation,

10101 XOR 01100 = 11001

Multiplication

Multiplication by x increases the power of each term by one. In the compact notation, this is equivalent to left bitwise shift.

(1x^4+0x^3+1x^2+0x^1+1x^0) * x = (1x^5+0x^4+1x^3+0x^2+1x^1+0x^0)
10101 << 1 = 101010

So, to multiply polynomials f(x) * g(x) we can multiply f(x) by each term of g(x) separately, each being equivalent to a shift, and then add, the addition being equivalent to XOR. Let’s multiply (x^4 + x^2 + 1) * (x^3 + x^2)

(x^4 + x^2 + 1) * (x^3 + x^2) = (x^4 + x^2 + 1)*x^3 + (x^4 + x^2 + 1) *x^2
(10101 << 3) XOR (10101 << 2) = 10101000 XOR 01010100 = 11111100

So, the answer is x^7 + x^6 + x^5 + x^4 + x^3 + x^2.

Modulo Reduction

Reduction modulo h(x) is also fairly easy. It certainly does not require you to remember how to do long division. Like multiplication, we’ll do it term by term. Let’s continue with the same example, and take it modulo h(x) = x^5 + x

(x^7 + ... + x^2) mod (x^5+x) = [x^7 mod (x^5+x)] + ... + [x^2 mod (x^5+x)]

Now, if the degree, n, of x^n is smaller than that of h(x), here 5, then there is nothing to be done because h(x) won’t divide x^n.

[x^2 mod (x^5+x)] = x^2 or 00000100
[x^3 mod (x^5+x)] = x^3 or 00001000
[x^4 mod (x^5+x)] = x^4 or 00010000

When then degrees are equal, we can say h(x) divides x^n one time, and we have overshot by the remaining terms of h(x). That we’ve overshot instead of undershot hardly matters, nor does the sign on remainder since -1 mod 2 = 1. Here,

x^5 = (x^5 + x) – x, so
[x^5 mod (x^5+x)] = x, or 00000010

In general, [x^n mod h(x)] = [h(x)-x^n] when n = degree(h). In compact form, this is equivalent to turning off the nth bit, which can be done by XOR-ing the representation of h(x) with the representation of x^n:

00100010 XOR 00100000 = 00000010.

When x^n has a degree larger than h(x) we can multiply h(x) by x^k to make the degrees match, and proceed as in the prior case.

x^6 = (x^5 + x)*x – (x)*x = -x^2, so [x^6 mod (x^5+x)] = x^2, or 00000100, or in compact form (00100010 << 1) XOR (00100000 << 1) = 00000100

But, more efficiently, just shift the previous answer, which we’ll do for x^7:

[x^7 mod (x^5+x)] = x^3, or 00001000

So to collect, we need to add these results, which is XOR-ing in the compact representation.

x^2 + x^3 + x^4 + x + x^2 + x^3 = x^4 + 2x^3 + 2x^2 + x = x^4 + x, or
00000100 XOR 00001000 XOR 00010000 XOR 00000010 XOR 00000100 XOR 00001000 = 00010010

Concluding Remarks

We can ask Wolfram Alpha to verify this result for us by long division. The remainder given is x^4 - x, which is equivalent to x^4 + x when the coefficients are modulo 2.

The term-by-term multiplication and modulo steps may be combined, e.g. multiply by x and modulo the product, for a more efficient algorithm, which will be a shift and XOR if the product’s degree is at least that of h(x). Then repeat on the result, multiply by x and modulo the product, and record that answer for multiplication by x^2. And so forth...