Modular Polynomial Arithmetic (Posted on 2008-04-16)

	Submitted by Brian Smith
Rating: 4.0000 (3 votes)
Solution:	(Hide)
x^2+x+1 is a factor of x^3-1. Let P(x) be a*x^n + b*x^(n-1) + c*x^(n-2) + d*x^(n-3) + q(x). Subtracting a*(x^3-1) from P(x) leaves P2(x) = b*x^(n-1) + c*x^(n-2) + (a+d)*x^(n-3) + q(x). Applying the subtraction repeatedly leaves a second degree polynomial R(x). The x^2 coefficient of R(x) is the sum of all the coefficients of x^2, x^5, . . . , x^(3k+2). Similarily the x coefficient of R(x) is the sum of all the coefficients of x, x^4, . . . , x^(3k+1). And the constant term of R(x) is the sum of the original constant term and all the coefficients of x^3, x^6, . . . , x^(3k). If the second degree polynomial is r*x^2 + s*x + t, then the remainder is (s-r)*x + (t-r). For example: P(x)=23x^10 - 8x^9 + 8x^8 + 7x^7 + 12x^6 - 6x^5 - 40x^4 + x^3 + x + 9 R(x) = (8-6+0)X^2 + (23+7-40+1)X + (-8+12+1+9) = 2x^2 + -9x + 14 remainder of P(x)/(x^2+x+1) = -11x + 12

	Subject	Author	Date
	Solution	Praneeth	2008-04-22 07:55:47
	plug in	Dennis	2008-04-17 11:12:52
	Simple examples	brianjn	2008-04-16 21:10:09
	re: Manipulate	brianjn	2008-04-16 20:21:00
	Manipulate	brianjn	2008-04-16 11:23:11