I'm trying to solve a rather specific problem involving quadratic residues. Let $p,q$ be primes $(q > 2)$, such that $p = 2q + 1$, i.e. p is a safe prime.
$\mathbb{Z}^{*}_{p}$ is a multiplicative group modulo $p$, having order $p-1$.
Next, consider the set $G = \{ x^{2} \bmod p \vert x \in \mathbb{Z}^{*}_{p} \}$. It can be shown that $G$, the set of quadratic residues modulo $p$, is a subgroup of $\mathbb{Z}^{*}_{p}$ having order $q$.
Let's consider two distinct elements $m_{0},m_{1} \in G$, where $m_{0} \neq m_{1}$, and consider the sets $G + m_{0}$ and $G + m_{1}$ where the addition is defined modulo $p$, i.e. $$G + m_{0} = \{ [g + m_{0}]\bmod p \vert g \in G \}$$ $$G + m_{1} = \{ [g + m_{1}]\bmod p \vert g \in G \}$$
I am trying to prove that $G + m_{0}$ and $G + m_{1}$ are distinct sets, i.e. their symmetric difference is non-empty.
Furthermore, if possible, I'm trying to find $m_{0},m_{1}$ that maximizes the cardinality of this symmetric difference, given the group $G$ and looking for an efficient algorithm that does this. I'm not sure if one exists.
The second problem is more of a bonus, which I won't be surprised if it's hard to solve. But the first problem (proving distinctness of the two sets) is pretty true I'm sure, except I'm not sure how to prove it.