  We consider the cyclotomic identity testing (CIT) problem: given a polynomial
$f(x_1,\ldots,x_k)$, decide whether $f(\zeta_n^{e_1},\ldots,\zeta_n^{e_k})$ is
zero, where $\zeta_n = e^{2\pi i/n}$ is a primitive complex $n$-th root of
unity and $e_1,\ldots,e_k$ are integers, represented in binary. When $f$ is
given by an algebraic circuit, we give a randomized polynomial-time algorithm
for CIT assuming the generalised Riemann hypothesis (GRH), and show that the
problem is in coNP unconditionally. When $f$ is given by a circuit of
polynomially bounded degree, we give a randomized NC algorithm. In case $f$ is
a linear form we show that the problem lies in NC. Towards understanding when
CIT can be solved in deterministic polynomial-time, we consider so-called
diagonal depth-3 circuits, i.e., polynomials $f=\sum_{i=1}^m g_i^{d_i}$, where
$g_i$ is a linear form and $d_i$ a positive integer given in unary. We observe
that a polynomial-time algorithm for CIT on this class would yield a
sub-exponential-time algorithm for polynomial identity testing. However,
assuming GRH, we show that if the linear forms~$g_i$ are all identical then CIT
can be solved in polynomial time. Finally, we use our results to give a new
proof that equality of compressed strings, i.e., strings presented using
context-free grammars, can be decided in randomized NC.
