Shifting quadratic residues modulo n

Question

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.

Answer 1

To maximise the size of the symmetric difference, you need to minimise the size of the intersection. A point in the intersection comes from nonzero $x$, $y\in\Bbb Z_p$ with $$x^2+m_0=y^2+m_1$$ in $\Bbb Z_p$. More precisely it comes from four such solutions as $(\pm x,pm y)$ all give the same number. So we are counting solutions of $$x^2-y^2=m_1-m_0$$ with $x$, $y\ne0$. Forgetting about the nonzero-ness condition the equation is $$(x-y)(x+y)=m_1-m_0$$ and as $m_1-m_1\ne0$ for each nonzero value of $x-y$, there's a unique $x+y$ so there are $p-1$ solutions.

But as $p\equiv3\pmod 4$, precisely one of $\pm(m_1-m_0)$ is a quadratic residue, and so there are two solutions with one of $x$, $y$ zero. So there are $\frac14(p-3)$ elements in $(G+m_0)\cap(G+m_1)$ no matter what $m_0$ and $m_1$ are. Thus the symmetric difference has size $p-1-\frac12(p-3)= \frac12(p+1)$.

Answer 2

The element $r=m_1-m_0\neq 0$ additively generates $\Bbb F_p$ so that $\mathcal T_r : t\mapsto t+r$ defines a permutation of $\Bbb F_p$ with only one cauchy cycle ; namely, the entire finite field $\Bbb F_p$ in some order.

Therefore, if $G = G + r$, i.e. $\mathcal T_r[G] = G$, then $G$ would have to contain a $\mathcal T_r$ orbit. But there is only one such orbit. This implies $\Bbb F_p\subset G$ and thus $p\leq|G| = \frac{p-1}{2}$ which is false.

$$G = G + r \implies \Bbb F_p\subset G\implies p\leq|G| = \frac{p-1}{2}$$

Therefore, $G\neq G+r$ and thus $G+m_0\neq G+m_1$.

The same argument holds for any distinct $m_0, m_1$ regardless of residuacity.