Algorithm to find primes $q$ and $p$ with $q\, |\, p - 1$? 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?
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&gt;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