# Symmetry for finite cyclic groups (Z/pZ)∗

How well is it known that for $i$ such that $1 \leq i \leq \frac{p − 1}2$:

$$g^{i+(p−1)/2} = g^{i−1+(p−1)/2} − g^i + g^{i−1} \pmod p$$

Whilst working in the finite cyclic group of prime moduli $(Z/pZ)^*$, given g to be a primitive root of p.

This property can be used to slightly improve the trial multiplication algorithm, see also http://eprint.iacr.org/2014/291

-
This question is currently a bit off-topic. WHY should cryptographers care about this relation? As a personal curiosity, where does this come from? – figlesquidge May 2 '14 at 9:43
@figlesquidge you are actually right, it probably is useless from the cryptography point of view, at least so far. It comes from eprint.iacr.org/2014/291, It would be nice for me to know if is a known property though , just for the sake of it :) – Antonio Sanso May 2 '14 at 9:52
I think you mean in the finite field $\mathbb F_p$, where $g$ is a generator of $\mathbb F_p^*$. – figlesquidge May 2 '14 at 10:25
fair enough. it theoretically slightly improve the trial multiplication algorithm (as worth as it is...) – Antonio Sanso May 2 '14 at 16:20

Yes, it is well-known, in the sense that it can be derived easily (not necessarily used). Note you probably meant for $g$ to be a primitive root of $p$, and the condition that $1 \leq i \leq (p - 1) / 2$ is not even required (any integer will do).

We start with the theorem that a primitive root $g$ of $p$ is always a quadratic nonresidue modulo $p$, so by Euler's criterion it follows that:

$$g^{(p - 1) / 2} \equiv -1 \pmod{p}$$

Multiplying each side by $g - 1 \in \mathbb{F}_p^*$ we obtain:

$$(g - 1) g^{(p - 1) / 2} \equiv -(g - 1) \pmod{p}$$

$$g g^{(p - 1) / 2} - g^{(p - 1) / 2} \equiv -g + 1 \pmod{p}$$

$$g^{1 + (p - 1) / 2} \equiv g^{(p - 1) / 2} - g + 1 \pmod{p}$$

Multiply through by $g^{i - 1}$ (for any $i \in \mathbb{Z}$) to obtain the required relation:

$$g^{1 + (p - 1) / 2 + i - 1} \equiv g^{(p - 1) / 2 + i - 1} - g^{1 + i - 1} + g^{i - 1} \pmod{p}$$

$$g^{i + (p - 1) / 2} \equiv g^{i - 1 + (p - 1) / 2} - g^{i} + g^{i - 1} \pmod{p}$$

In fact, the result holds whenever $g$ is a quadratic nonresidue of $p$. It just happens to be always the case for primitive roots, and given the problem statement that seems to already be a precondition on $g$. If on the other hand $g$ is a quadratic residue of $p$ then we get a similar, but different result.

-
thanks Thomas, while not used I found this symmmetry kind of nice (while probably useless) – Antonio Sanso May 2 '14 at 11:08