Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
finite_fields:07_multiplicative_group [2014/01/20 11:23] marje |
finite_fields:07_multiplicative_group [2016/02/24 01:10] jaan grammar fixes |
||
|---|---|---|---|
| Line 119: | Line 119: | ||
| The red arrows forming the circle show that the element $0111 = \alpha^2+\alpha+ 1$ indeed generates the multiplicative subgroup. Each blue arrow corresponds to multiplication by $0010 = \alpha$ and each gray arrow corresponds to multiplication by $1101 = \alpha^2 + \alpha + 1$. As the blue arrows form a pentagon and the gray arrows a triangle, the orders of $0010$ and $1101$ are $5$ and $3$, respectively. | The red arrows forming the circle show that the element $0111 = \alpha^2+\alpha+ 1$ indeed generates the multiplicative subgroup. Each blue arrow corresponds to multiplication by $0010 = \alpha$ and each gray arrow corresponds to multiplication by $1101 = \alpha^2 + \alpha + 1$. As the blue arrows form a pentagon and the gray arrows a triangle, the orders of $0010$ and $1101$ are $5$ and $3$, respectively. | ||
| - | Actually it is easy to tell whether an element $x$ is the generator of the multiplicative group or not, if it is represented as a power of a generator, i. e. in the form $x = a^k$. For example, $1101 = 0111^{5}$, thus multiplication of an element by $1101$ means multiplication by $0111$ repeated $5$ times, i. e. one gray arrow is equivalent to jumping forward by $5$ in the red cycle. Now note that the group order $15$ is exactly divisible by $5$, so, starting from the identity element $0111^0 = 0001$ and following the gray arrows, we will after $15/5=3$ jumps be back at the beginning and thus $1101$ has no chance of generating the whole multiplicative group. With the element $0010$ it's a little less obvious why it cannot be a generator, since $0010 = 0111^6$ but $15$ is not divisible by $6$. However, note that $15$ and $6$ have a common divisor $3$ and thus, if we start going from the identity element, then even after wrapping around modulo $15$, the blue arrows can only reach elements $0111^k$, where $k$ is divisible by three. | + | Actually it is easy to tell whether an element $x$ is a generator of the multiplicative group or not, if it is represented as a power of a generator, i. e. in the form $x = a^k$. For example, $1101 = 0111^{5}$, thus multiplication of an element by $1101$ means multiplication by $0111$ repeated $5$ times, i. e. one gray arrow is equivalent to jumping forward by $5$ in the red cycle. Now note that the group order $15$ is exactly divisible by $5$, so, starting from the identity element $0111^0 = 0001$ and following the gray arrows, we will after $15/5=3$ jumps be back at the beginning and thus $1101$ has no chance of generating the whole multiplicative group. With the element $0010$ it's a little less obvious why it cannot be a generator, since $0010 = 0111^6$ but $15$ is not divisible by $6$. However, note that $15$ and $6$ have a common divisor $3$ and thus, if we start going from the identity element, then even after wrapping around modulo $15$, the blue arrows can only reach elements $0111^k$ where $k$ is divisible by three. |
| <WRAP task> | <WRAP task> | ||