Fast constructive recognition of a black box group isomorphic to \(S_n\) or \(A_n\) using Goldbach's conjecture (Q1971492)

This paper deals with the following question: Suppose you have a finitely generated group \(G\) for which you know that there exists a group isomorphism \(\phi\colon G\to S_n\), where \(S_n\) is the symmetric group. Can you construct \(\phi\) ``quickly'' and, if so, how? The authors provide a ``randomized'' algorithm which computes \(a,b\in G\) such that \(\phi(a)=(1,2)\) and \(\phi(b)=(1,2,\dots,n)\). Moreover, they provide an algorithm which, for each \(x\in G\), computes \(\phi(x)\in S_n\). These algorithms, and their complexity estimates, involve several assumptions -- all of which are laid out clearly by the authors. For example, they assume \(n\geq 20\) and, for the complexity estimates, a rather explicit version of the Goldbach 2-primes conjecture. Under these assumptions, their algorithms are sub-quadratic in \(n\). The authors give a modification of their algorithm where \(S_n\) is replaced by \(A_n\). They also address the harder question: what if one knows only that there exists a group isomorphism \(\phi\colon G\to S_n\), for some unknown \(n\)? The authors show that, under the Goldbach conjecture, there is a subquadratic (randomized) algorithm to do that, too.