Finding Generator of finite field The task is to show that $x^2 + 1$ is irreducible over $\mathbb{F}_{743}$ and then find a generator of  $\mathbb{F}_{743}[x]/(x^2+1)$.
This question has already been asked but not really answered 
here
I've shown that $x^2+1$ is irreducible, since $ 743 \equiv 3\pmod{4}$ and therefore $-1$ is not a quadratic residue mod 743.
But I don't understand how to find a generator of $\mathbb{F}_{743}[x]/(x^2+1)$. I assume I need to look for an element of order $743^2-1$, but is there an obvious way to do this, or is it just done by trying? 
 A: Unless you are particularly persistent software assistance is recommended. Educated guessing does help, so I will share my approach. A bit of divide and conquer. I saw this as an exercise in trying to minimize computer aid, but you are welcome to have mixed feelings about the wisdom of that :-)
The main observation is that in a cyclic group of order $n$ an element $g$ is a generator unless $g^{n/p}=1$ for some prime $p\mid n$.
First we probably want a generator of $K=\Bbb{F}_{743}$. The law of quadratic reciprocity says that both $2$ and $3$ are squares in this field but $5$ is not, so let's test $5$ more carefully. Here $n=742=2\cdot7\cdot53$, and because $5$ is not a square $5^{n/2}\neq1$. We do need to check the exponents $n/7=106$ and $n/53=14$. Mathematica (or Wolfram Alpha) tells me that
$$
5^{14}\equiv212\pmod{743}\qquad\text{and}\qquad 5^{106}\equiv 433\pmod{743},
$$
so we can conclude that $5$ is a generator of $K^*$.
We move on to the extension field $L=K[x]/\langle x^2+1\rangle$. For easier notation I will denote the coset of $x$ modulo $x^2+1$ by $i$ so the familiar rule $i^2=-1$ holds. Another piece of theory is the use of automorphisms. Clearly "complex conjugation" $a+bi\mapsto a-bi$ is a non-trivial automorphism of $L$. But we also know that the Frobenius automorphism is the only non-trivial automorphism of a quadratic extension of the prime field. Therefore, for all $a,b\in K$ we have
$$
(a+bi)^{743}=a-bi.
$$ 
It follows that 
$$
(2+i)^{744}=(2+i)^{743}(2+i)=(2-i)(2+i)=5.
$$
This already gives us a reason so suspect that $g=2+i$ might be a generator of $L^*$.
The order of $L^*$ is $N=742\cdot744=2^4\cdot3\cdot7\cdot31\cdot53$, so we have five primes to consider. Let us denote the order of $g$ by $m$. We know that the order
of $g^{744}$ is $742$. On the other hand, if $c$ is an element of order $\ell$
in a multiplicative, it is well known that (covered in a first course on cyclic groups)
$$
\operatorname{ord}(c^k)=\frac{\ell}{\gcd(\ell,k)}.
$$
Together with the known order $742$ of $g^{744}$ we see that
$$
2\cdot7\cdot53=742=\frac{m}{\gcd(m,744)}.
$$
This implies that $m$ is divisible by both $7$ and $53$, so we don't need to test those primes.
Could it be that $g^{N/p}=1$ for any of the remaining prime factors $p\in\{2,3,31\}$ of $N$? An element $z\in L^*$ has order that is a factor of $742$ if and only if $z\in K^*$. If $g^{N/31}=1$ it follows that the order of $g^{744/31}=g^{24}$ must be a factor of $742$. In other words, for this to happen we must have $g^{24}\in K$.
But a calculation modulo $743$ shows that
$$
(2+i)^{24}=302+357i\notin K.
$$
Similarly, $g^{N/3}=1$ implies that $g^{744/3}=g^{248}\in K$. Again, a calculation
shows that
$$
(2+i)^{248}=-237-251i\notin K.
$$
The last prime factor $p=2$ is shared by $742$ and $744$. Therefore it is easy for
$$
(2+i)^{N/2}=(2+i)^{744\cdot(742/2)}=5^{742/2}.
$$
We already knew that $5$ is a generator $K^*$, so this power is not trivial (in fact, it must be equal to $-1$).

Conclusion: $2+i$ is a generator of $L^*$. Aided by a bit of algebra we managed to keep the set of exponents we had to test a bit lower. Not sure whether the tricks brought the exponents to a range, where you might be willing to paper & pencil calculate them, for example by the good old square-and-multiply.

A: The algorithm is probabilistic: try elements $\alpha$ of $\Bbb F_{743}[x]{/}(x^2+1)$ and check if $\alpha^{\frac{n}{2}} = -1$, where $n=|\Bbb F^\ast_{743}[x]{/}(x^2+1)|=743^2 - 1 = 552048$. If this holds we've found our generator. 
Some computer assistance seems required. (Pari or some such program). (I normally start with $\alpha=x$ as a try, next, maybe $x+1$ or $x-1$ etc.)
