Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi all, we have some important news to share. Please follow the link here to find out more!

https://www.boards.ie/discussion/2058419143/important-news/p1?new=1

Multiplicative inverse - what am I doing wrong?

  • 05-07-2008 11:16PM
    #1
    Closed Accounts Posts: 12,382 ✭✭✭✭


    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!]


Comments

  • Closed Accounts Posts: 6,081 ✭✭✭LeixlipRed


    To find the inverse of some a (mod n) you use the fact that an inverse exists if and only if the gcd of a and n is one.


  • Closed Accounts Posts: 12,382 ✭✭✭✭AARRRGH


    Hi LeixlipRed

    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!


Advertisement