Given two elements $A,B \in \text{SL}(2, \mathbb{F}\_{2^n})$, is there a (computationally inexpensive) test one could perform to check whether together they generate the entire group?



Testing whether two elements of $\text{SL}(2, \mathbb{F}_{2^n})$ generate the entire group
The answer is **yes**, it is *easy to check* whether the ordered pair $(A, B)$ generates $\text{SL}\_2(\mathbb{F}\_q)$ for $q$ the power of a prime number. Indeed, there exist *simple criteria* according to Daryl McCullough and Marcus Wanderley, see [1, Section 11]. (*Italic* means that I am quoting the authors).



> 
> 
> > 
> > **Claim.**
> >  The pair $(A, B)$ generates $\text{SL}\_2(\mathbb{F}\_q)$ if and only if
> >  $$\text{Tr}(A, B) \Doteq (\text{Tr}(A), \text{Tr}(B), \text{Tr}(AB))$$ is an essential triple, i.e.,
> >  doesn't satisfy any of the conditions $(1) - (5)$ of [1, Section 11].
> > 
> > 
> > 
> 
> 
> 


For instance, the condition $(1)$ for a triple $(\alpha, \beta, \gamma) \in \mathbb{F}\_q^3$ holds if at least two of $\alpha, \beta$ and $\gamma$ are zero. The image in $\text{PSL}\_2(\mathbb{F}\_q)$ of a pair $(A, B) \in \text{SL}\_2(\mathbb{F}\_q)^2$ such that $\text{Tr}(A, B) = (\alpha, \beta, \gamma)$ generates a dihedral group in this case.
Condition $(2)$ holds if $\alpha^2 + \beta^2 + \gamma^2 - \alpha \beta \gamma - 2 = 2$, the left-hand side being the *Fricke polynomial*. This corresponds to the case of an *affine subgroup of $\text{PSL}\_2(\mathbb{F}\_q)$*, that is a subgroup which is conjugate to a subgroup of the image in $\text{PSL}\_2(\mathbb{F}\_q)$ of the subgroup of upper triangular matrices in $\text{SL}\_2(\mathbb{F}\_q)$.
Condition $(4)$ holds if $\alpha, \beta$ and $\gamma$ lie in a proper subfield of $\mathbb{F}\_q$. The remaining conditions are presented in the Addendum below. 


It follows from the claim that OP's decision problem boils down to:



> 
> * deciding whether two elements of $\mathbb{F}\_q$ are equal.
> * deciding whether $k$ elements of $\mathbb{F}\_q$ ($k \le 4$) generate a proper subfield.
> * deciding whether an element of $\mathbb{F}\_q$ belongs to a subfield of $\mathbb{F}\_q$ generated by $k$ given elements ($k \le 4$).
> 
> 
> 


The above claim follows from a theorem of Macbeath [1, Theorem 8.2] while the criteria are based on Dickson's Theorem [1, Theorem 6.1] and another theorem of Macbeath [1, Theorem 8.1].


**Side note.**
Let $G$ be a finite group generated by $k$ elements.
Let $\varphi\_k(G) = \frac{\vert \text{Epi}(F\_k, G) \vert}{\vert \text{Hom}(F\_k, G) \vert}$, where $F\_k$ denotes the free group on $k$ generators. The ratio $\varphi\_k(G)$ is the probability that two uniformly chosen random elements generate $G$. 
By a theorem of Liebeck and Shalev, we have $\lim\_n \varphi\_2(G\_n) = 1$ for any sequence of non-isomorphic finite simple groups, see [3, Theorem 1.1.1]. For a simple group $G\_n(q)$ of Lie type of untwisted rank $n$, we have 
$\varphi\_2(G\_n(q)) = 1 - O(\frac{n^3 \log^2(q)}{q^n})$ by results of Kantor, Lubotzky, Liebeck and Shalev, see [3, Theorem 1.1.2].


**Addendum.**
Let $Q(\alpha, \beta, \gamma) \Doteq \alpha^2 + \beta^2 + \gamma^2 - \alpha \beta \gamma - 2$ be the *Fricke polynomial*. This name was coined because of Fricke's trace identity $$\text{Tr}([A, B]) = Q(\text{Tr}(A), \text{Tr}(B), \text{Tr}(AB)).$$
Here are the five conditions derived by Daryl McCullough and Marcus Wanderley from Dickson's Subgroup Classification Theorem and Macbeath's Fricke polynomial criterion:



> 
> $(1)$ *Dihedral case.* At least two of $\alpha, \beta$ and $\gamma$ are zero. 
> 
> 
> $(2)$ *Affine case.* $Q(\alpha, \beta, \gamma) = 2$.
> 
> 
> $(3.A\_4)$ The elements $\alpha, \beta$ and $\gamma$ lie in $\{-1, 0, 1\}$ and $Q(\alpha, \beta, \gamma) = 0$. 
> 
> 
> $(3.S\_4)$ The elements $\alpha, \beta$ and $\gamma$ lie in $\{\pm 1, \pm \sqrt{2}\}$ and $Q(\alpha, \beta, \gamma) = 1$, where $\sqrt{2}$ denotes one root of $X^2 - 2$.
> 
> 
> $(3.A\_5)$ It's complicated! The authors redirect us to [2, Main Theorem (3)].
> 
> 
> $(4)$ *Affine or $SL\_2(q')$.* The elements $\alpha, \beta$ and $\gamma$ lie in a proper subfield of $\mathbb{F}\_q$. 
> 
> 
> $(5)$ *Affine or $SL\_2(q')$ or $PGL\_2(q')$.* The integer $q$ is odd, $\alpha^2,\beta^2,\gamma^2$ and $\alpha \beta \gamma$ lie in a proper subfield $\mathbb{F}\_{q'}$ of $\mathbb{F}\_q$ and at least one of $\alpha, \beta$ and $\gamma$ does not lie in $\mathbb{F}\_{q'}$.
> 
> 
> 


The cited article (a very nice paper!) contains more details, and of course, the corresponding proofs.




---


[1] D. McCullough, M. Wanderley, "Nielsen equivalence of generating pairs of $\text{SL}(2, q)$", 2013.


[2] D. McCullough, "Exceptional subgroups of $\text{SL}(2, F )$". Preprint available [here](http://www.math.ou.edu/~dmccullough/research/manuscripts.html), accessed 4 January 2013.


[3] I. Pak, "What do we know about the product replacement algorithm?", 2000.


