Let $n$ be an odd positive integer of unknown factorization, and let $x$ be relatively prime to $n$. The Jacobi symbol $\left(\frac{x}{n}\right)$ gives me partial information on whether $x$ is a square modulo $n$ (in particular, if $\left(\frac{x}{n}\right)=-1$, then $x$ is certainly not a square). Also, the Jacobi symbol can be evaluated efficiently (in polynomial time), given $x$ and $n$ as input, without needing to know the factorization of $n$.
Is there a generalization of the Jacobi symbol that gives me information about whether $x$ is a $k$th power modulo $n$, when $k>2$? And if so, can it be computed in polynomial time, given $x$ and $n$ as input, without knowing the factorization of $n$? In particular, is there any known generalization that satisfies both of these criteria (gives me information about whether $x$ is a $k$th power; computable efficiently without knowing the factorization of $n$)?
You can focus on the case where $k$ divides $\varphi(n)$, since the other cases follow straightforwardly from that one.
There are a pair of generalizations.
You are looking for either the power residue symbol or the Hilbert symbol (which are very closely related).
These should be computable, since computing norms of ideals in number fields is a reasonable computation. For highly composite moduli you would need to be able to factor, but this problem is present for the Jacobi symbol too.