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

For my crypto assignment, I'm asked to enter a prime P and generate Q such that Q|P-1

Can anyone guide me what is Q|P-1?

share|improve this question
That notation means $Q$ divides $P-1$. In other words, divide $P-1$ by $Q$, is there a remainder, if so then $Q$ does not divide $P-1$, if not then $Q$ divides $P-1$. – mikeazo Nov 7 '14 at 16:28
That means that Q divides P-1. – DrLecter Nov 7 '14 at 16:28
BTW, there is a very simple answer that works for all primes but one. – mikeazo Nov 7 '14 at 16:29
Will the result of q be a prime? or can it be a composite? – Calvin Peh Nov 7 '14 at 16:30
Assuming this is about generating a finite field with a subgroup of order Q, we usually choose Q first, then choose a r such that P=Q*r+1 with P of appropriate size. Repeat with different Q or r until P is prime. That way you don't need to do any factoring. For Diffie-Hellman we often choose r=2 and vary Q, for signatures fixing Q and varying r can be preferable. – CodesInChaos Nov 7 '14 at 21:20
up vote 1 down vote accepted

It means $Q$ divides $P-1$. In other words, $P-1$ is a multiple of $Q$.

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.