Polynomial CongruenceDate: 02/28/2001 at 03:14:14 From: David Kwan Subject: Polynomial Congruence I am having a problem understanding how to solve a polynomial congruence. Here is the problem: Find a polynomial (F) in Field(7) with degree less then 4. ( x^2 -1 ) F == ( x^3 + 2x + 5 ) mod ( x^4 + 2x^2 + 1) Please help to find F. I looked at many topics on linear congruence but none talked about polynomials. Date: 02/28/2001 at 15:36:46 From: Doctor Rob Subject: Re: Polynomial Congruence Thanks for writing to Ask Dr. Math, David. You need to find the multiplicative inverse of x^2 - 1, so that you can multiply both sides by this to isolate F on one side of the congruence. You do this by using the Euclidean Algorithm, starting with inputs x^4 + 2*x^2 + 1 and x^2 - 1: x^4 + 2*x^2 + 1 = (x^2 - 1)*(x^2 + 3) + 4. Since the remainder is a constant, you are ready to backtrack: 1 = 2*4 (mod 7) = 2*[(x^4 + 2*x^2 + 1) - (x^2 + 3)*(x^2 - 1)] (mod 7), = 2*(x^4 + 2*x^2 + 1) - 2*(x^2 + 3)*(x^2 - 1) (mod 7), = 2*(x^4 + 2*x^2 + 1) + (5*x^2 + 1)*(x^2 - 1) (mod 7), 1 = (5*x^2 + 1)*(x^2 - 1) (modd x^4 + 2*x^2 + 1, 7). That means that 5*x^2 + 1 is the multiplicative inverse of x^2 - 1. Now multiply both sides of your original congruence by 5*x^2 + 1, and reduce both sides modulo x^4 + 2*x^2 + 1, and also reduce all coefficients modulo 7, and you'll have your answer. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ Date: 02/28/2001 at 17:28:41 From: David Kwan Subject: Re: Polynomial Congruence Thank you, Doctor Rob, for answering the question for me. But I have one more step to clarify, on the second step to third step. We have 2*(x^4 + 2*x^2 + 1) - 2*(x^2 + 3)*(x^2 - 1) (mod 7) which becomes 2*(x^4 + 2*x^2 + 1) + (5*x^2 +1)*(x^2 - 1) (mod 7) How does -2*(x^2 + 3)*(x^2 - 1) become (5*x^2 + 1)*(x^2 - 1) ? Or can we just have -2(x^2 + 3) as the inverse? David Date: 03/01/2001 at 11:45:32 From: Doctor Rob Subject: Re: Polynomial Congruence Thanks for writing back, David. -2*(x^2 + 3) = -2*x^2 - 6 = 5*x^2 + 1 + 7*(-x^2 - 1). When you reduce coefficients modulo 7, the last part reduces to zero. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/