I think that since ord_4 27 is 9, we only need to take the cases from P(1), P(2), ..., P(9)...

Isn't this just we define $P(x) = -4^n$ for $n = 0, 1, 2, \dots, 26$ (such a $P(x)$ of degree 28 exists by Lagrange's Interpolation Formula) and then $P(a) \equiv P(b) \pmod {27}$ if and only if $a \equiv b \pmod {27}$ (because $a - b | P(a) - P(b)$) does the rest?

ummm degree 28 or degree 26? but then the polynomial is not necessarily an integer polynomial!

suli wrote: Isn't this just we define $P(x) = -4^n$ for $n = 0, 1, 2, \dots, 26$ (such a $P(x)$ of degree 28 exists by Lagrange's Interpolation Formula) and then $P(a) \equiv P(b) \pmod {27}$ if and only if $a \equiv b \pmod {27}$ (because $a - b | P(a) - P(b)$) does the rest? Not sure, but can you adopt your solution to make the polynomial an integer polynomial; i.e. with all integer coefficients?

I have a very nice solution for this: Use the Binomial theorem: $$4^n=(3+1)^n \equiv 1+3\binom{n}{1}+9\binom{n}{2} \pmod{27}$$ because the other terms are divisible with $27$. So using $2^{-1}\equiv 14\pmod{27}$: $$4^n \equiv \frac{9n^2-3n+2}{2} \equiv 14(9n^2-3n+2) \pmod{27}$$ So we can choose our polynomial to be : $$P(X)=-126X^2+42X-28$$