modulo operation for polynomials?

[smslca]

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

[science_man_88]

Originally Posted by smslca

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 would try this by finding the first exponent where (x+1)^y > (x^5)-1 find the mod there and then use floor(1729/y) as a power of that modulo and go from there the hard part for me is finding the first part with variable x.

[jasonp]

Polynomial division works just like integer division, except that each term is treated independently of all the others, so there are no carries from one term to the next. So modular exponentiation of polynomials can use the same algorithms as exponentiation of integers.

If the denominator polynomial is monic (i.e. leading coefficient is 1) then the remainder will always have degree less than the denominator. When an intermediate polynomial gets a coefficient of x^5, subtract that coefficient times the denominator polynomial. If the numerator has a leading coefficient x^k larger than x^5, pretend you're dividing integers and subtract off

(coefficient of x^k) * x^(k-5) * denominator(x)

to kill off the x^k term, then repeat with lower order terms until the remainder is less than the denominator.

[R.D. Silverman]

Originally Posted by jasonp

Polynomial division works just like integer division, except that each term is treated independently of all the others, so there are no carries from one term to the next. So modular exponentiation of polynomials can use the same algorithms as exponentiation of integers.

If the denominator polynomial is monic (i.e. leading coefficient is 1) then the remainder will always have degree less than the denominator. When an intermediate polynomial gets a coefficient of x^5, subtract that coefficient times the denominator polynomial. If the numerator has a leading coefficient x^k larger than x^5, pretend you're dividing integers and subtract off

(coefficient of x^k) * x^(k-5) * denominator(x)

to kill off the x^k term, then repeat with lower order terms until the remainder is less than the denominator.

I have suggested repeatedly that anyone wanting to discuss computer
arithmetic or algebra be required to read Knuth Vol II before posting.