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...

Answer 2

This is a knowledge question. Basically, unless you either are as smart as Gauss or you already know congruence mathematics, also known as "modular arithmetic", you are screwed. One book you may want to read to learn about this stuff is "Introduction to Number Theory with Computing" by Allenby.

Ultimately the key knowledge is that the congruence can be calculated by several methods, the best of which is the "square and multiply" method which is quite ancient. Basically, whenever you have a binary 1 you both square and multiple, but when you have a 0, you just square. The complete algorithm and explanation is on p. 79 of Allenby.

Another approach would use the Chinese Remainder Thereom, which is probably what the questioner was aiming at.

Where are you applying? The NSA? Los Alamos? That is a pretty tough question.

---

Great, downvoted for being the only person who actually answered the question. Just to be clear here: undoubtedly the interviewer was expecting exploitation of the square and multiply algorithm, as I said above. Square and multiply is used inside of RSA/cryptography algorithms to do fast modulo operations. See p. 225 for a description of this algorithm and RSA application: Implementation of Multinomial Standard Product for RSA State. The interviewer probably worked on RSA which is why he knew of the method.

Answer 3

This looks like a simple polynomial multiplication and long division problem. Just multiply the polynomials and then divide them. Multiplication is pretty straightforward with two nested for loops, for long division see:

http://www.sosmath.com/algebra/factor/fac01/fac01.html

http://en.wikipedia.org/wiki/Polynomial_long_division

Answer 4

What you're essentially doing is binary operations. You can look at how your CPU implements such operations.

http://en.wikipedia.org/wiki/Multiplication_algorithm http://en.wikipedia.org/wiki/Modulo_operation