# Why gcd(r,(p-1)/r) needs to be 1 in benaloh cryptosystem

I recently discovered the benaloh cryptosystem. I am working with the system as it is discribed in the following link: https://en.wikipedia.org/wiki/Benaloh_cryptosystem

However I need some help in order to understand why we need $${gcd(r,(p-1)/r)}$$

As far as I understand the condition $$r \mid (p-1)$$ guarantees the existence of the subgroup of order (p-1)/r which contains the r-residues.

The third condition

$${gcd(r,(q-1))}$$

allows us to say that there are

$$\mid \mathbb{Z}_n^* \mid /r$$ r-residues mod n.

what does the other condition add?

• You need those conditions to be sure that $r^2 \not | \phi(n)$ – ddddavidee Jan 14 '16 at 21:40
• why is this important here? – user28082 Jan 14 '16 at 22:10
• otherwise your secret key $x$ would be a $r$-residue. and the decryption would not work. I'll try to write down the whole in a complete answer during next weekend. – ddddavidee Jan 14 '16 at 22:16

$gcd(r,(p-1)/r)$ needs to be $1$ in Benaloh cryptosystem that mean that $(r)$ and $(p-1)$ are preliminary among them.
• then what you say is not true. $gcd(r,(p−1)/r)$ only says that $r$ and $(p-1)/r$ are prime between them. But surely not that $r$ and $p-1$ are prime between them (which is not the case by the way). This doesn't seem to be an answer to my initial question why we need this condition. – user28082 Jan 17 '16 at 22:23