You cannot have a field with 269 elements.
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
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.
[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!]
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.
(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?
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 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...
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
Like let a be a polynomial and b be multiplicative inverse.so according to definition of multiplicative inverse
You might need to rationalize RHS in some cases.
Remember there is no multiplicative inverse of 0 as 1/0 is undefined.
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?
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?
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.
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?