Results 1 to 15 of 15

Math Help - Multiplicative inverse - what am I doing wrong?

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    25

    Multiplicative inverse - what am I doing wrong?

    Hello

    This should be easy, but I am being stupid I think.

    • I have a finite field with 269 fields.
    • I want to find the multiplicative inverse of 98.
    • I multiply 98 by every field in the finite field (modulo 269) until the answer is 1.
    • This gives me 140.
    • (98 * 140) modulo 269 = 1

    Grand.

    However, I thought I could use the multiplicative inverse instead of division? For example, instead of dividing a number by 98 (modulo 269) I could multiply it by 140 (modulo 269). This doesn't seem to be working.

    Am I doing something stupid?

    Any help appreciated.

    Thanks

    [One more question if anyone can help! If the numbers I am dealing with are polynomials, can I use the same system as above, except use polynomial multiplication instead of natural number multiplication? Thanks!]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    You cannot have a field with 269 elements.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2008
    Posts
    25
    Thanks for your reply.

    The number of elements in my fields needs to be prime. 269 is prime.

    Why do you feel I can't have 269 elements in my finite field?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MrSteve View Post
    Thanks for your reply.

    The number of elements in my fields needs to be prime. 269 is prime.

    Why do you feel I can't have 269 elements in my finite field?
    Sorry, made a mistake. The number just did not look prime.

    You want to solve 98x\equiv 1(\bmod 269).
    You can add the modulos, 98x\equiv 270(\bmod 269).
    Now simplify, 49x\equiv 135(\bmod 269)
    Subtract modulos 3 times, 49x\equiv -672(\bmod 269).
    Simplfy, 7x\equiv -96(\bmod 269).
    Subtract modulos 3 times, 7x\equiv -903(\bmod 269).
    Simplify again, x\equiv -129(\bmod 269)\implies x\equiv 140(\bmod 269).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2008
    Posts
    25
    Thanks for your reply. I really appreciate you taking the time to answer my questions.

    OK - so 140 is indeed the multiplicative inverse of 98.

    However...

    (100 / 98) mod 269 = 1.02
    (100 * 140) mod 269 = 12

    Shouldn't the two answers be the same, i.e. instead of dividing by 98 I can multiply by 140?

    Am I totally lost?

    Thanks
    Last edited by MrSteve; July 6th 2008 at 11:29 AM. Reason: Typo
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MrSteve View Post
    Thanks for your reply. I really appreciate you taking the time to answer my questions.

    OK - so 140 is indeed the multiplicative inverse of 98.

    However...

    (100 / 98) mod 269 = 1.02
    (100 * 140) mod 269 = 12
    The problem is you are thinking of 1/98 as an element in \mathbb{Q} you should be thinking of it as an element of \mathbb{Z}_{296}. We define a/b to be ab^{-1}. Thus, 100/98 = 100\cdot 98^{-1} = 100\cdot 140 = 12.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Apr 2008
    Posts
    25
    Ah ok, thank you.

    Do you mind me asking you another question?

    I need to use the multiplicative inverse of a number (or to be exact, of a binary polynomial) when I want to divide, i.e. I am not allowed divide so I need to use the multiplicative inverse instead.

    So if a is 1011 0000 (x^7 + x^5 + x^4) and b is 0011 1000 (x^5 + x^5 + x^3), and I need to divide a by b, should I get the multiplicative inverse of b and multiply a by b instead?

    Won't that just cause the same problem I had in my post #5 above?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MrSteve View Post
    I need to use the multiplicative inverse of a number (or to be exact, of a binary polynomial) when I want to divide, i.e. I am not allowed divide so I need to use the multiplicative inverse instead.

    So if a is 1011 0000 (x^7 + x^5 + x^4) and b is 0011 1000 (x^5 + x^4 + x^3), and I need to divide a by b, should I get the multiplicative inverse of b and multiply a by b instead?
    It is the same idea. The problem is I do not know where this "binary polynomial" is from. I can see it has coefficients in \mathbb{Z}_2 (because it is binary) but I do not see what field you are working in. To make my question more clear, what does (x^5+x^4+x^3)^{-1} mean? It means a binary polynomial f(x) such that (x^5+x^4+x^3)f(x) = 1. The problem is that it is impossible to make that product 1 because it needs to have degree at least 5. Therefore, division is not possible. However, if p(x) is an irreducible binary polynomial then \mathbb{Z}_2[x]/(p(x)) is a field and therefore (x^5+x^4+x^3)f(x) = 1 has a solution, and therefore division is possible. You need to specify over what irreducible polynomial you are working with.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Apr 2008
    Posts
    25
    Thanks for the reply.

    Let's assume the field size is 7, so the highest power the polynomial can have is 7. The irreducible polynomial is x^7 +x^6 + 1.

    I am using a binary field (i.e. the coefficient is either 1 or 0) and the powers in the polynomials are stored as binary. I simply divide by the irreducible polynomial to keep all calculations within my finite field.

    The problem is I am not allowed divide (as the group I am using is an additive and multiplicative group) so I need to figure out another way to divide. My solution is to multiply by the multiplicate inverse of an element instead of dividing by that element.

    Currently I am still trying to figure out how to generate the multiplicative inverse of a polynomial. I am thinking of using the following -

    Input: a, f
    Output: the inverse of a

    1. u <- a, v <- f
    2. g1 <- 1, g2 <- 0
    3. while u != 1 do
    3.1 j <- deg(u) - deg(v)
    3.2 if j < 0 then: u <-> v, g1 <-> g2, j <- - j
    3.3 u <- u + (z^j)v
    3.4 g1 <- g1 + (z^j)g2
    4. Return g1

    where <- means "becomes", <-> means "swap contents", deg means "return the highest power", and - j means "change the sign of j".

    This seems to be the extended Euclidean algorithm.

    ...

    Being totally honest, I barely understand this stuff, and unfortunately I don't really have anyone to talk to about it! I am a part-time student and my professors are not elliptic curve experts or mathematicians...

    I know how to "brute force" find the multiplicative inverse of a number (using my method from post #1). I'm guessing I can use this same method to multiply my binary polynomial by every other element in the field until one of the calculations returns 1, but it would be very inefficient...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    For finding the multiplicative inverse of a number, use the Euclidian algorithm.
    We know that a remainder in the division will be the gcd at a moment.

    See here for an example : http://www.mathhelpforum.com/math-he...102-post3.html

    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Apr 2008
    Posts
    25
    Thank you for the reply.

    I think I am ok with the concept of getting the inverse of a number, but the inverse of a polynomial?

    Is it the exact same concept?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    290
    Quote Originally Posted by MrSteve View Post
    Thank you for the reply.

    I think I am ok with the concept of getting the inverse of a number, but the inverse of a polynomial?

    Is it the exact same concept?
    though it may already have been said but remember multiplicative inverse of a mathematical quantity like an expression,number etc is a mathematical quantity of same nature which when multiplied to the given mathematical quantity gives 1.
    Like let a be a polynomial and b be multiplicative inverse.so according to definition of multiplicative inverse
    ab=1 therfor
    b=1/a.
    You might need to rationalize RHS in some cases.
    Remember there is no multiplicative inverse of 0 as 1/0 is undefined.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Apr 2008
    Posts
    25
    Quote Originally Posted by ThePerfectHacker View Post
    What does (x^5+x^4+x^3)^{-1} mean? It means a binary polynomial f(x) such that (x^5+x^4+x^3)f(x) = 1. The problem is that it is impossible to make that product 1 because it needs to have degree at least 5. Therefore, division is not possible. However, if p(x) is an irreducible binary polynomial then \mathbb{Z}_2[x]/(p(x)) is a field and therefore (x^5+x^4+x^3)f(x) = 1 has a solution, and therefore division is possible. You need to specify over what irreducible polynomial you are working with.
    I have been thinking a little bit more about your answer. As I am working withing a finite field, I do have an irreducible polynomial.

    However I have only ever used the irreducible polynomial to keep the powers of my polynomials within a certain range.

    Would you mind explaining (with an example, if possible) how I would use the irreducible polynomial during multiplicative inverse?

    For example:

    a = x^7 + x^5 + x + 1
    b = x^6 + x^2 + x

    Irreducible polynomial = x^11+x^4+x^2+x+1

    a / b = x^7 + x^5 + x + 1 / x^6 + x^2 + x = 1 remainder x^5 + x^2 + x
    a * (inverse b) = x^7 + x^5 + x + 1 * (inverse b) = 1 remainder x^5 + x^2 + x

    How can I figure out the inverse of b?
    Where does the irreducible polynomial come in to play?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Apr 2008
    Posts
    25
    Ah... figured it out.

    This link might be useful for other readers: Math Forum - Ask Dr. Math

    Thanks for the help everyone!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Junior Member
    Joined
    Apr 2008
    Posts
    25
    Right, one more question then I'll leave you alone!

    Would you mind telling me if this looks right to you?

    I want to find the multiplicative inverse of x^4 + 1. The irreducible polynomial I am using is x^8 + x^6 + x^5 + x + 1.

    I have already worked out (using Extended Euclidean Algorithm) that the multiplicative inverse of x^4 + 1 is x^6 + x^4 + x^3 + x^2 + 1.

    So -

    f(x) = x^8 + x^6 + x^5 + x + 1
    a = x^4 + 1
    1/a = x^6 + x^4 + x^3 + x^2 + 1

    This is how I verified I am correct -

    a * 1/a = x^10 + x^8 + x^7 + x^3 + x^2 + 1

    As this is larger than f(x), I divide it by f(x) and keep the remainder -

    (a * 1/a) / f(x) = x^2 remainder 1

    The remainder 1 means the multiplicative inverse of a is x^6 + x^4 + x^3 + x^2 + 1, as a * 1/a = b mod f(x) = 1.

    Does this sound correct?

    Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Multiplicative Inverse
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2011, 11:48 AM
  2. multiplicative inverse
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2010, 01:31 PM
  3. Multiplicative Inverse of...
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 29th 2009, 09:06 PM
  4. Multiplicative Inverse?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 27th 2007, 10:43 AM
  5. Multiplicative inverse
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 14th 2006, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum