# Thread: Multiplicative inverse - what am I doing wrong?

1. ## 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!]

2. You cannot have a field with 269 elements.

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?

4. Originally Posted by MrSteve

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)$.

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

6. Originally Posted by MrSteve

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$.

7. 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

8. Originally Posted by MrSteve
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.

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...

10. 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

11. 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?

12. Originally Posted by MrSteve

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.

13. Originally Posted by ThePerfectHacker
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?

14. Ah... figured it out.

Thanks for the help everyone!

15. 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!