I understand that if $p$ is prime then $p-1$ must be composite (at least divisible by $2$ as it is even). But how does an algorithm find a prime $q$ such that $q \cdot r = p - 1$. I thought prime factorisation is such a hard problem?

  • $\begingroup$ what are the restrictions on $q$? $q=2$ is always a solution $\endgroup$ – qwr Aug 19 '19 at 17:09
  • $\begingroup$ @qwr You are obviously right. $q$ is supposed to be a great prime. The common reccomendation for crypto algorithms seems to be that the bit-width of $p$ is about 3 or 4 times the bit-width of $q$. $\endgroup$ – Linus Aug 20 '19 at 10:43

The critical facts enabling to find such $p$ in practice are:

  • We can easily tell with practical certainty if an integer with many thousand bits is prime or not, using a primality test such as Miller-Rabin, even though we are typically unable to tell all its factors when it is not prime.
  • About $1.4/b$ integers of $b$ bits are prime. Thus it is more likely than not that randomly trying $b$ integers of $b$ bits will uncover a prime (for $b>4$).

Hence a possible method to find a somewhat random large prime $p$ with some large known random prime $q$ dividing $p-1$ is:

  • first randomly select a suitably large prime $q$
  • for successive $r$ of suitable size
    • compute $p\gets q\,r+1$
    • if $p$ is prime
      • output $p$ and stop.

There are refinements to this. Obviously, we can restrict to even $r$. That's a special case with $s=2$ of a more general tweak: for any small prime $s$, it must hold that $q\,r+1\bmod s\ne0$, thus $r\bmod s\ne-q^{-1}\bmod s$. This allows to build a sieve of possible $r$, eliminating most candidates without a full primality test.

There are standardized algorithms to generate such $p$ and $q$, including deterministically from a seed. See FIPS 186-4 appendix A.1

| improve this answer | |
  • $\begingroup$ Hey, thanks for the quick reply! This answers all my questions. :-) $\endgroup$ – Linus Aug 19 '19 at 6:55

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.