Multiplicative inverse - what am I doing wrong?

AARRRGH

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

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.

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!