Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

One of the necessary components to the Schnorr Digital Signature scheme is a pair of prime numbers $p$ and $q$ such that $q$ divides $p-1.$ However, there is never a modular inverse taken of q so why is there an extra constraint on $q$? Couldn't $q$ be a number that divides $p-1$ but not prime?

share|improve this question
up vote 3 down vote accepted

First of all, while Schnorr Signatures are usually described that way, the two primes are not necessary for it to work. In principle, Schnorr works in any cyclic group.

However, to achieve security we need that the discrete logarithm problem in that group is hard. So the reason for the choice of $q$ (which is the group order) is that DL is believed to be hard in subgroups of prime order $q$ of $\mathbb{Z}_p^*$, where p is a safe prime, i.e. $p=2q+1$. (And also for other values than $2$, but I'm currently not sure what the conditions are.)

share|improve this answer

Your Answer


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.