What algorithm is Mathematica 9 using for
The help page of GroupElementToWord shows that it has a Method option. The documentation for that option says that "GroupElementToWord uses the Minkwitz algorithm, with a number of parameters", and shows some examples on how changing those parameters can result in shorter words in the generators.
The Minkwitz algorithm (Torsten Minkwitz, 1998) is based on the construction of a table of coset representatives of the group stabilizers associated to a given base of the group. Constructing this table may take some time for large groups, but once the table is available it will be fast to factorize new elements of that group.
For example, generate some random group:
Take a random element of that group and factorize it:
Now take another element of the same group and factorize it. This time the computation is faster:
I am just sharing my small idea here and someone can correct me if I am wrong somewhere. Computational group theory algorithms are used in mathematical software. Group is never stored as it is in any data structure and actually generated on the run using its generating sets.