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