# How can I generate large primes for Pedersen commitment?

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.

• Possible duplicate of How to efficiently generate a random safe prime of given length? Dec 27, 2018 at 14:34
• 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. Dec 27, 2018 at 16:08
• As i stated, I'm interested in primes fit for pedersen's commitment. It requires large primes Dec 27, 2018 at 17:19
• For pre-existing constants, one possibility is the 2048-bit $p$ and 256-bit $q$ from section 2.3 of RFC 5114.
– fgrieu
Dec 27, 2018 at 18:10

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.