Jnfqqub

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