For the PDP scheme, I need to generate the following parameter: g is a generator of Q (Q is the set of quadratic residues modulo N (N = pq is the RSA modulus) What algorithm can be used to generate this parameter most effectively?

  • $\begingroup$ All but answered there. $\endgroup$ – fgrieu May 14 '19 at 9:43
  • $\begingroup$ To summarize the answer: pick $p, q$ to be distinct safe primes ($(p-1)/2, (q-1)/2$ are also prime), then pick an arbitrary $r$ and set $g = r^2 \pmod{pq}$; as long as $\gcd(pq, g-1) = 1$, then $g$ will generate the entire group. If you don't want to bother messing with $r$, you can just note that $g=4$ will work... $\endgroup$ – poncho May 14 '19 at 13:05

Your Answer

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

Browse other questions tagged or ask your own question.