0

As the GF(19) gets pretty lengthy by just writing each element in terms of each element powers, is there any other method to solve this?

Charan Presence
  • 23

3 Answers3

2

So to find the order of each element I have no choice but to calculate it for all the 18 elements?

Not exactly: you have to find a primitive element $a$. All elements in $\mathbf F_{19}^\times$ are a power $a^k$. Now the order of $a^k$ is $$\operatorname{ord}(a^k)=\frac{\operatorname{ord} a}{\gcd(k,\operatorname{ord}a)},$$ so $a^k$ is also a primitive element if and only if $k$ is coprime to $\operatorname{ord}a=18$, i.e. $k$ is one of $\:1,5,7,11,13,17$.

Trying with $2$, we compute its first powers $\bmod 18$. As its order is a divisor of $18$, we only have to compute its powers up to $9$: if its order is $>9$, it is equal to $18$. Indeed, we have this table of the relevant powers of $2$: \begin{matrix} k&2&3&6&9\\ \hline 2^k&4&8&64\equiv7&8\cdot 7\equiv-1 \end{matrix} so $2$ is a primitive element, and the other primitive elements are $$2^5=32\equiv \color{red}{13},\;2^7\equiv 13\times4\equiv\color{red}{14},\; 2^{11}\equiv 13^2\cdot2\equiv-4\equiv\color{red}{15},\;2^{13}\equiv -4^2=\color{red}{3},\;2^{17}\equiv3\cdot16\equiv \color{red}{10}.$$

Bernard
  • 175,478
1

Essentially, brute force is the only method. There is no fast algorithm for finding primitive roots. But you don't have to calculate for every element separately. Start with the powers of $2$. If you happen to get $18$ different values before reaching $1$ you're done, since you have a generator of that cyclic group ( a primitive root). If not, then pick an element you don't see and work with it.

For example, using the residue system $(-9, 10)$ (so that i never deal with big numbers) the powers of $2$ are $$ 2, 4, 8, 16 \equiv -3, -6, -12 \equiv 7, 14 \equiv -5, -10 \equiv 9, 18 \equiv -1. $$ Having found the first $9$ powers and not seeing $1$ means $2$ is a primitive root. Then the other primitive roots are $2^a$ when $\gcd(a,18) = 1$ and it's easy to find the orders of everything else too.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • So to find the order of each element I have no choice but to calculate it for all the 18 elements? Thanks for your answer btw – Charan Presence Oct 03 '19 at 21:04
  • @CharanPresence To know it for each element you have to compute it somehow for each element. – Mark Bennet Oct 03 '19 at 21:31
  • @MarkBennet is right. but the "somehow" need not start from scratch for each element. You can leverage calculations you've already done. See my edit. – Ethan Bolker Oct 03 '19 at 21:35
  • @EthanBolker Indeed, it is question of efficient calculation. I was being pedantic. I have put a different answer, specific to this case, but with elements which could be generalised - going via computing squares and cubes. – Mark Bennet Oct 03 '19 at 22:08
0

The orders of elements are $1,3,9,2,6,18$. There are equal numbers of elements of odd and even order. Every element of odd order is a square.

Note that $-1$ is the only element of order $2$. If $a$ has odd order $r$, then $(-a)^r=-1$ and $-a$ has order $2r$.

So we compute the squares $1,4,9,16, 25=6, 36=17, 49=11, 64=7, 81=5$ hence $1,4,5,6,7,9,11,16,17$

Now squares have odd order, so order $1, 3, 9$. There is one element of order $1$ and two of order $3$ and six of order $9$. Identify which have order $3$ and you know them all. Their negatives have double the order. You can do this directly by cubing to identify $7$ and $11$ as the elements of order $3$. Another way to do this is to compute the cubes (there are six of these since $18$ is divisible by $3$) ie $\pm 1, \pm 8, (\pm 27=\pm 8), \pm 64=\pm 7$ or $1,7,8,11,12,18$. The cubes have orders $1,2,3,6$ one each of order $1$ and $2$, and two elements of order $3$ and two elements of order $6$.

This identifies $7$ and $11$ as being the elements of order $3$ (comparing with the list of squares)

So order $1$: $1$

Order $2$: $-1=18$

Order $3$: $7; 11$

Order $6$: $-7=12; -11=8$

Order $9$ (the squares not yet listed): $4; 5; 6; 9; 16; 17$

Order $18$ (primitive roots):$2; 3; 10; 13; 14; 15$

I think this is the kind of thing you mean.

Alternatively you can work as follows:

It is pretty obvious that $4^3 \neq 1$, so $4$ must have order $9$ and its negative $-4=15$ must be a primitive root (order $18$).

Now also $(-2)^2$ has order $9$ and $-2=17$ is a square, so $-2$ has order $9$ and $2$ has order $18$.

and continue until you have enough information.

To get the numbers of elements of each order note that the multiplicative group here is cyclic and has one subgroup of each order which divides the order of the group.

Alternatively factorise $$x^{18}-1=(x^9+1)(x^9-1)=(x^3+1)(x^6-x^3+1)(x^3-1)(x^6+x^3+1)=$$$$=(x+1)(x^2-x-1)(x^6-x^3+1)(x-1)(x^2+x+1)(x^6+x^3+1)$$ and note that the factors belong to elements of degrees $2;6;18;1;3;9$ respectively.

You can identify the elements of order $3$ therefore as roots of $x^2+x+1=0$ or $4x^2+4x+4=(2x+1)^2+3=0$. Now $-3=16$ is a square and $$2x+1=\pm 4; x=\frac 32=11 \text { or } x=-\frac 52=7$$

I spotted this much later, but if I had caught it earlier, I could have worked out all the orders by computing the squares and solving this one quadratic.

Note that you don't have to do the full factorisation to identify the quadratic for the cubes - just identify the factor $x^3-1= (x-1)(x^2+x+1)$

Mark Bennet
  • 100,194
  • So the strategy here is to identify the squares (nine computations, all simple) as the elements of odd order, and then identify the cube roots of $1$ (easiest way, solve the quadratic if you don't spot them). This tells you the elements of order $1$ and $3$ directly and order $9$ by elimination. Their negatives have order $2; 6; 18$ respectively. The same method works for any prime of form $6q+1$ where $q$ is an odd prime, and requires the identification of $\frac {q-1}2$ squares (in large cases quadratic reciprocity might help) and the solution of the quadratic $x^2+x+1=0$. – Mark Bennet Oct 04 '19 at 08:27