-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This question is currently a bit off-topic. WHY should cryptographers care about this relation? As a personal curiosity, where does this come from? $\endgroup$ – figlesquidge May 2 '14 at 9:43
  • $\begingroup$ @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 :) $\endgroup$ – Antonio Sanso May 2 '14 at 9:52
  • $\begingroup$ I think you mean in the finite field $\mathbb F_p$, where $g$ is a generator of $\mathbb F_p^*$. $\endgroup$ – figlesquidge May 2 '14 at 10:25
  • $\begingroup$ fair enough. it theoretically slightly improve the trial multiplication algorithm (as worth as it is...) $\endgroup$ – Antonio Sanso May 2 '14 at 16:20
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.