Inversion of the $j$--function and testing complex multiplication

We develop an algorithm to invert the $j$–function in quasilinear time, and apply this to testing whether an elliptic curve has complex multiplication.