Deciding whether a given number is a totient or nontotient

Question

The following algorithm decides if a number $n>0$ is a totient or a nontotient:

if n = 1
  return true
if n is odd
  return false
for k in n..n^2
  if φ(k) = n
    return true
return false

This is very slow; even using a sieve it takes $n^2$ steps to decide that $n$ is nontotient. Is there a fast method? Polynomial (in $\log n$) would be best but is probably too much to hope for.

---

Edit: I was able to adapt this

totient(n,m=1)={
    my(k,p);
    if(n<2,return(n==1));
    if(n%2,return(0));
    fordiv(n,d,
        if(d<m|!isprime(p=d+1),next);
        k=n\d;
        while(1,
            if(totient(k,p), return(1));
            if(k%p,break);
            k\=p
        )
    );
    0
};

from Max Alekseyev's $\varphi^{-1}$ script, which is substantially faster than the pseudocode above.

Answer 1

This seems to be a hard problem. See https://mathoverflow.net/questions/31691/inverting-the-totient-function (but that post is about inverting $\phi$, not deciding whether there is a solution).

Answer 2

There are many references to track down at http://oeis.org/A005277