I can improve your test. This works without assuming Lehmer's conjecture:
Let x be a positive integer.
If f(x) = x1 return PRIME
If f(x) < x1 return COMPOSITE
If f(x) > x1 return UNIT
Now all you have to do is find a way to compute f(x) quickly and you're done!
