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?
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$).