This question is inspired by this challenge on CodeGolf.SE, in which the goal is to create a hash function with specified collisions. I thought a polynomial over the integers mod $n$ might be a nice solution, but realized I didn't know a good way to come up with one.
Let me phrase the question as follows. Let $n$ be an integer and let $R$ be the ring $\mathbb{Z} / n \mathbb{Z}$. I do not wish to assume that $n$ is prime (I have in mind $n = 2^{32}$). Let $A \subset R$ with $x_1 \in A$ and $x_2 \in R \setminus A$. Let $m = |A|$ and assume $m \ll n$.
Problem. Find a polynomial $p$ over $R$, of minimum degree, such that $p(x_1) = p(x_2)$ and the restriction $p|_A$ is injective.
Is there an efficient algorithm for this problem?
Trivially we can find a solution of degree $m$, by setting $p$ to take whatever values we desire on $A \cup \{x_2\}$. But since I don't care what values $p$ takes on $A$, so long as they are distinct, it seems we might be able to reduce the degree a lot. For all I know, there might even be a solution of degree 3.
A crude approach might be to be take $p(x) = (x-x_1)(x-x_2)q(x)$, where $q$ is some random polynomial, and check exhaustively whether $p|_A$ is injective. Given that $m \ll n$, it seems that this would succeed with high probability, but it is inelegant, and it might not be easy to ensure that $p$ was of minimum degree.
Of course, the question might also be interesting with $R$ replaced by another finite commutative ring. We could also ask to be able to prescribe more values for $p$ outside $A$.
If $n\mid k^2$ and $p\in\mathbb Z/n\mathbb Z[X]$ with $p(0)=p(k)$, then $p(0)=p(2k)$.
Proof: Consider the polynomial $q(X)=p(kX)-p(0)$. We have $q(0)=q(1)=0$. We can drop all monomials of degree $\ge 2$, hence as a function $q(X)$ is like $aX+b$ with $a.b\in\mathbb Z/n\mathbb Z$. From $q(0)=q(1)=0$, we have $a=b=0$, hence $p(2k)=q(2)=0$. $_\square$
Corollary: If additionally $n\not\mid 2k$, no polynomial for $A=\{0,2k\}$, $x_1=0$, $x_2=k$ exists.