Let $G$ be a finite group. Define the Hurwitz action of $B\_{n}$ on $G^{n}$ by letting
$(x\_{1},...,x\_{n})\sigma\_{i}=(x\_{1},...,x\_{i}x\_{i+1}x\_{i}^{-1},x\_{i},x\_{i+2},...,x\_{n})$. I wonder what algorithms exist that produce a small circuit $C$ such that
$C(x\_{1},...,x\_{n})=(x\_{1},...,x\_{n})b$ for all $x\_{1},...,x\_{n}\in G$.


$\textbf{Algorithm 1:}$ Let $b$ be a braid. Then a braid word $w$ representing $b$ is said to be a geodesic braid word if $w$ has minimal length among all braids that represent $b$. The set of all braids in $B\_{\infty}$ is a $co-NP$-complete problem. However, while the geodesic braid word of a braid $w$ is $co-NP$-complete, in practice, there is an approximate algorithms for finding nearly geodesic braid words for a braid.


In particular, in [this paper](http://www.sci.ccny.cuny.edu/~shpil/kl_attack.pdf), the authors have observed that Dehornoy's handle reduction usually replaces a braid word $w$ with an equivalent but shorter braid word $w'$. The authors therefore proposed alternating between left handle reductions and right handle reductions as an algorithm for finding very short braid words $w^{\sharp}$ for a given braid $b$. Therefore, when we consider the nearly geodesic braid word $w^{\sharp}$ as a circuit, then the word $w^{\sharp}$ is a quite short circuit that computes $(x\_{1},...,x\_{n})\mapsto(x\_{1},...,x\_{n})b$.


$\textbf{Possible algorithm 2: The fast Hurwitz action}$


Let $\Delta\_{n}=(\sigma\_{1}...\sigma\_{n-1})(\sigma\_{1}...\sigma\_{n-2})...
(\sigma\_{1}\sigma\_{2})\sigma\_{1}$. Then $\Delta\_{n}$ is known as the fundamental braid.


Then while the braid $\Delta\_{n}$ has $\frac{n(n-1)}{2}$, elements, the action
$(x\_{1},...,x\_{n})\mapsto(x\_{1},...,x\_{n})\Delta\_{n}$ can be computed by performing $O(n)$ many group operations on $G$ (instead of the $O(n^{2})$ operations which one has to do if one applies the braid $\Delta\_{n}$ directly).


Suppose that $(x\_{1},...,x\_{n})\in G$. Then compute $(y\_{1},...,y\_{n})$ recursively by letting $y\_{1}=e$ and $y\_{n+1}=y\_{n}\cdot x\_{n}$. Then
$$(x\_{1},...,x\_{n})\Delta\_{n}=(y\_{n}x\_{n}y\_{n}^{-1},y\_{n-1}x\_{n-1}y\_{n-1}^{-1},...,y\_{2}x\_{2}y\_{2}^{-1},y\_{1}x\_{1}y\_{1}^{-1}).$$ Therefore, one obtains a fast algorithm for computing $(x\_{1},...,x\_{n})\Delta\_{n}$ using $O(n)$ group operations rather than $O(n^{2})$ group operations. The fast Hurwitz action also allows us to compute
$(x\_{1},...,x\_{n})(\sigma\_{1}...\sigma\_{i\_{1}})...(\sigma\_{1}...\sigma\_{i\_{k}})$ where $i\_{1}>...>i\_{k}$ in $O(n)$ steps as well.


Is there any way to generalize this fast Hurwitz action to other braids? Does there exist a braid form in which one is able to easily apply the fast Hurwitz action or a generalized fast Hurwitz action? Is there a good way to in general decompose a braid $b$ as the composition of braids in which one can apply the fast Hurwitz action? If algorithm 2 can be applied to all braids in a reasonable manner, does algorithm 2 in general use more or less gates than algorithm 1?


The braids $(\sigma\_{1}...\sigma\_{i\_{1}})...(\sigma\_{1}...\sigma\_{i\_{k}})$ look very similar to the simple braids which one obtains from the Garside normal form of a braid, but I have not yet been able to apply the fast Hurwitz action to simple braids in general.


$\textbf{A possible application to cryptography}$ If one defines the length $\ell(b)$ of the braid $b$ to be the number of gates in a suitably optimized circuit $C$ with $C(x\_{1},...,x\_{n})=(x\_{1},...,x\_{n})b$, then the length function $\ell$ may be useful in constructing length based attacks against various braid group cryptosystems. However, one needs to optimize the circuit size $\ell(b)$ in order for this length based attack to be effective.



How quickly can one compute the Hurwitz action of braid groups on finite groups?
I have good news. The Hurwitz action of a simple braid or the inverse of a simple braid from a tuple on a group takes $O(n\cdot\log(n))$ many group operations which is much better than the $O(n^{2})$ many operations it would take using the bubblesort-like Hurwitz action algorithm.


In particular, the Hurwitz action of a braid $b$ which can be written as the composition of $k$ simple braids in $B\_{n}$ takes $O(k\cdot n\cdot\log(n))$ many group operations.


Let $G$ be a finite group and let $(x\_{1},\dots,x\_{n})\in G^{n}$. Let $b$ be a simple braid. For easier-to-read code, we shall assume that $n=2^{N}$ for some $N$.


The following code in the programming language GAP returns the output of the action
$(x\_{1},...,x\_{n})\cdot b$ where `list` denotes $(x\_{1},...,x\_{n})$ and where if `perm` denotes the array $(f(1),...,f(n))$ where $f=\pi(b)$ where $\pi:B\_{n}\rightarrow S\_{n}$ is the projection to the semigroup. The following algorithm shall be called the fast Hurwitz action.



```
fastactionsimple:=function(perm,list)
n:=Length(perm);
N:=LogInt(n,2);
output:=[];
tree:=[list];
for i in [1..N-1] do
    tree[i+1]:=[];
    for j in [1..Length(tree[i])/2] do
        tree[i+1][j]:=tree[i][2*j-1]*tree[i][2*j];
    od;
od;
for i in [1..n] do
    a:=perm[i];
    b:=tree[1][a];
    aa:=a;
    tree[1][a]:=();
    for j in [2..N] do
        aa:=(aa+RemInt(aa,2))/2;
        if 2*aa<=Length(tree[j-1]) then
            tree[j][aa]:=tree[j-1][2*aa-1]*tree[j-1][2*aa];
        else
            tree[j][aa]:=tree[j-1][2*aa-1];
        fi;
    od;
    v:=();
    bin:=0;
    for j in Reversed([1..N]) do
        if (bin+1)*2^(j-1)<=a then v:=v*tree[j][bin+1]; bin:=(bin+1)*2;
        else bin:=bin*2;
        fi;
    od;
    output[i]:=v*b*v^(-1);
od;
return output;
end;

```

Remark: The following example illustrates how to make further improvements to compute the Hurwitz action even quicker. Let $T\_{r}$ denotes the collection of all transpositions in $S\_{r}$. Then computing the group operation in $S\_{r}$ takes $O(r)$ time which makes the fast Hurwitz action on $S\_{r}$ take take $O(nr\cdot\log(n))$ time which may be worse than the $O(n^{2})$ time that the standard Hurwitz action would take. Luckily, one can modify the above algorithm so that the Hurwitz action $(x\_{1},...,x\_{n})\cdot b$ where $b$ is simple and $x\_{1},...,x\_{n}\in T\_{r}$ can be computed in $O(n\cdot\log(n))$ time by a straightforward modification to the algorithm for the fast Hurwitz action.


