# Complexity of finding automorphism group of code

What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code? Is there better bound on complexity if structure of code is known for eg. Reed Muller codes, goppa codes, quasi-cyclic codes, hadamard etc?

Here is reminder for definition of aut group for code generated by Generator matrix G

$$aut({G})= (A,P) :AGP=G$$

By taking direct sum of codes (given their two generator matrices $$G_1, G_2$$, consider the block matrix $$G_1 \oplus G_2 = \begin{bmatrix} G_1 & 0 \\ 0 & G_2 \end{bmatrix}$$), finding the automorphism group is at least as hard as testing isomorphism of codes (also called code equivalence). The current best upper bound for testing equivalence of linear codes is $$2^{O(n)}$$ (see Babai-Codenotti-G-Qiao, SODA '11), and this algorithm can in fact give you generators for the automorphism group.
• "Random" here is in a very specific technical sense, not in the colloquial sense of "arbitrary." The technical sense of "random" here means: "If you choose a code of length n purely at random (from some specified, natural distribution that's too long to write in this comment), the probability that the SSA works in poly(n) time is 1-f(n) where $\lim_{n \to \infty} f(n) = 0$." – Joshua Grochow Feb 6 '20 at 6:05
• I think reduction you provided in answer is classic one. Any standard reference I can cite for this? Also, if I understand reduction process correctly, it shows that if code automorphism for length $2n$ to equivalence over codes of length $n$ as a class. Clearly, it is sufficient for efficiency purposes. But what would be implications of showing statements like code equivalence for $G_{1},G_{2}$ can be solved then $aut(G_{1})$ can be found? That is instance to instance statement not class to class? – Root Feb 13 '20 at 16:46