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