Determining an inner automorphism via queries Let $G$ be a group. You are given that $\phi$ is some inner automorphism of $G$, i.e, $\phi(x) = axa^{-1}$ for some $a \in G$ uniquely determined modulo the center of the group. You're not sure what $a$ is, but you have a machine that can magically compute $\phi(x)$ on individual values of $x$. Is there a good algorithm/procedure for figuring out what $a$ is (modulo the center) by making queries to this machine?
I'd really be interested in answers for any structures with notions of inner automorphisms. An application which interests me is the following: Suppose $\phi$ is some automorphism of a central simple algebra over a field which I have some nice description for which makes it easy to compute. By the Skolem-Noether Theorem, I know $\phi$ is actually inner. Can I figure out what element $\phi$ conjugates by?
 A: You could ask for the values of $\phi$ on a generating set of $G$ of smallest possible size. That would determine $\phi$ and hence $a$ modulo the centre. It is unlikely that you will find a better general solution than that.
Of course in specific groups, you might be able to calculate $a$ with fewer images. The extreme case is when $G$ is abelian, when you don't need to amke any queries, and any element $a$ is a correct answer.
So you would need to restrict the class of groups $G$ under consideration. I guess you are looking for a collections of elements $x_i$ of $G$ such that the intersection of their centralizers is the centre of $G$. 
A: Two observations. If you know enough about your situation to be able to quotient out the center, that would be useful, since a unique solution is easier to find than a non-unique solution.
Second, if you have a faithful f.d. linear representation of your group, that would be helpful, because,  by your queries, you have a lot of equations: 
$$
a x_i - y_i a = 0,
$$
where $(x_i, y_i)$ are data and $a$ is the unknown.  This are linear equations for the unknown matrix $a$.   From the point of view of linear algebra, you may even get more useful information from any one query because $a x_i^k = y_i^k a$ for all $k$.
I don't know if this is only theoretical speculation, or if you actually want to do computations.  If the latter, the big mathematics packages (Mathematica. ...)  seem to have built in routines for this type of equation.
