Results 1 to 5 of 5

Math Help - modulo operation for polynomials?

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    11

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by ssnmanikanta View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2010
    Posts
    11
    Thanks opalg. It's the answer am waiting for. Thank you so much.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2
    Quote Originally Posted by ssnmanikanta View Post
    Thanks opalg. ...
    There's a button for that!
    (It's in the lower left corner of each post)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by TheChaz View Post
    There's a button for that!
    (It's in the lower left corner of each post)
    Thanks Chaz! (I count those thankses obsessively.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Operation @
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: April 2nd 2010, 12:10 AM
  2. Operation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 24th 2010, 08:20 PM
  3. Replies: 2
    Last Post: December 18th 2009, 01:48 PM
  4. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 10:04 AM
  5. row operation
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 17th 2007, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum