Sunday, November 8, 2015

finite fields - is it meaningful to calculate (x+1)x+2 in GF(32), e.g. using discrete logs?



I'm teaching myself about algebra and fields and I've just started playing with discrete logarithms.




I constructed GF(32) using the polynomials degree <2 and arithmetic modulo the irreducible polynomial (x2+1). Then I built a table of logs to the base of the primitive element (2x+2).



I can see that the log function maps only the non-zero elements of the field, so it seems sensible to use modulo 8 arithmetic between log values. This seems to work - for example:



log2x+2((2x+1)2modx2+1)=(2×log2x+2(2x+1))mod8log2x+2(x)=(2×(7))mod86=6




But how should I calculate, for example, (x+1)(x+2) ? Clearly modulo 8 arithmetic isn't going to do the trick. I guess that I need to use an irreducible polynomial but I am uncertain as to which one. Can I just use (x2+1) again?


Answer



Obviously, (1+x)x+2 should be (1+x)x(1+x)2, but there's no consistent way to define (1+x)x.



All the nonzero elements of the finite field are given by 1,1+x,(1+x)2,,(1+x)7, so whatever (1+x)x is, we have (1+x)x=(1+x)k for some integer k.



As a result, (1+x)x2=[(1+x)k]x=[(1+x)x]k=[(1+x)k]k=(1+x)k2. But we also know that (1+x)x2 should be (1+x)1=(1+x)7, because (1+x)x2(1+x)=(1+x)x2+1=1. So whatever k is, it must satisfy k^2 \equiv 7 \pmod 8; but there is no such integer.



(In other words, f(a) = a^x should satisfy f(ab) = f(a)f(b) and f(f(a)) = a^{-1}, but the above proves that there is no such f.)


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...