Sunday, November 8, 2015

finite fields - is it meaningful to calculate $(x+1)^{x+2}$ in $GF(3^2)$, 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($3^2$) using the polynomials degree $<2$ and arithmetic modulo the irreducible polynomial $(x^2 + 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:



$$\begin{align}
\log_{2x+2}\big({(2x+1)^2}_{mod\,x^2+1} \big)&=\big(2\times \log_{2x+2}(2x+1)\big)_{mod\,8}\\
\log_{2x+2}(x) &= \big(2 \times (7)\big)_{mod\,8}\\
6&=6
\end{align}$$




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 $(x^2+1)$ again?


Answer



Obviously, $(1+x)^{x+2}$ should be $(1+x)^x \cdot (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, \dots, (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)^{x^2} = [(1+x)^k]^x = [(1+x)^x]^k = [(1+x)^k]^k = (1+x)^{k^2}$. But we also know that $(1+x)^{x^2}$ should be $(1+x)^{-1} = (1+x)^7$, because $(1+x)^{x^2}(1+x) = (1+x)^{x^2+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...