I want to make a commitment on Shamir's Secret Sharing, based on the work of Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing".

To implement the commitment protocol, I need two LARGE primes $q$ and $p$ such that $q \mid (p-1)$. How can one generate such primes?

Note: This is different from generating a safe prime since I'm required to generate a prime with specific characteristics.

  • 1
    $\begingroup$ Possible duplicate of How to efficiently generate a random safe prime of given length? $\endgroup$
    – Maeher
    Commented Dec 27, 2018 at 14:34
  • $\begingroup$ As currently posed the question is probably incorrect. If interpreted literally: Choose any prime $p$ and set $q=2$. There's probably done restriction on the size of $q$. And in that case it's just a slight generalization of finding a safe prime. $\endgroup$
    – Maeher
    Commented Dec 27, 2018 at 16:08
  • $\begingroup$ As i stated, I'm interested in primes fit for pedersen's commitment. It requires large primes $\endgroup$
    – Curve25519
    Commented Dec 27, 2018 at 17:19
  • $\begingroup$ For pre-existing constants, one possibility is the 2048-bit $p$ and 256-bit $q$ from section 2.3 of RFC 5114. $\endgroup$
    – fgrieu
    Commented Dec 27, 2018 at 18:10

1 Answer 1


You can find two algorithms for generating such $p$ and $q$ in Appendix A.1, FIPS-186-4 (digital signature standard).

edited to add: Essentially, the two algorithms generate a pseudorandom prime number $q$ of the desired size first, then generate a pseudorandom random number $p$ (such that $q|(p-1)$) of the desired size, and test whether $p$ is prime. If so return $(p,q)$ pair, otherwise start over again. The difference between the two algorithms is that the one in A1.1 uses probabilistic primality testing thus returns probable prime numbers and the one in A1.2 returns provable prime numbers. The two algorithms use hash functions as pseudorandom generators so that the seed can be provided for people to verify the numbers are generated pseudorandomly from the seed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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