Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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 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 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 at 10:25
    
fair enough. it theoretically slightly improve the trial multiplication algorithm (as worth as it is...) –  Antonio Sanso May 2 at 16:20
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
thanks Thomas, while not used I found this symmmetry kind of nice (while probably useless) –  Antonio Sanso May 2 at 11:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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