# Thread: modulo operation for polynomials?

1. ## modulo operation for polynomials?

I know , how to calculate " x mod p " for a given very large "x" value and some p value. Here , x and p are integers

But how can we calculate f(x) mod g(x) , for which f(x) has higher degree(or order) than g(x).
And that degree turns out to be a very large number.

Ex:[ (x+1)^1729 mod ((x^5)-1) ] or [ (x+1)^1729 mod (1729,((x^5)-1)) ]

Is there any method or algorithm to calculate it at faster speeds

2. Originally Posted by ssnmanikanta
I know , how to calculate " x mod p " for a given very large "x" value and some p value. Here , x and p are integers

But how can we calculate f(x) mod g(x) , for which f(x) has higher degree(or order) than g(x).
And that degree turns out to be a very large number.

Ex:[ (x+1)^1729 mod ((x^5)-1) ] or [ (x+1)^1729 mod (1729,((x^5)-1)) ]

Is there any method or algorithm to calculate it at faster speeds
I don't know of any general method for doing this. In the particular case of reducing (x+1)^1729 modulo x^5–1, I would use the fact that 12^3 = 1728. So start by computing (x+1)^12. In that polynomial of degree 12, replace x^5 by 1, x^6 by x, x^7 by x^2 and so on, x^10 by 1 again, x^11 by x and x^12 by x^2. You then have a quartic polynomial congruent to (x+1)^12 mod (x^5–1). Cube it to get a degree 12 polynomial congruent to (x+1)^{12^3} mod (x^5–1). Then multiply the result by x+1, and finally reduce mod (x^5–1) again to get a quartic polynomial congruent to (x+1)^1729 mod (x^5–1). That shouldn't take too long to compute.

For a general power of x+1, a more systematic method is to express the power in binary form. For example, 1729 = 2^10 + 2^9 + 2^7 + 2^6 + 1. Then by successive squaring, you can compute the powers (x+1)^{2^n} inductively, reducing mod (x^5–1) as you go along, so that each of these powers will be a quartic polynomial. Then multiply the appropriate ones together to get (x+1)^1729.

3. Thanks opalg. It's the answer am waiting for. Thank you so much.

4. Originally Posted by ssnmanikanta
Thanks opalg. ...
There's a button for that!
(It's in the lower left corner of each post)

5. Originally Posted by TheChaz
There's a button for that!
(It's in the lower left corner of each post)
Thanks Chaz! (I count those thankses obsessively.)