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
    Dec 27 '18 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
    Dec 27 '18 at 16:08
  • $\begingroup$ As i stated, I'm interested in primes fit for pedersen's commitment. It requires large primes $\endgroup$
    – Curve25519
    Dec 27 '18 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
    Dec 27 '18 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.


Your Answer

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

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