# 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?

• what are the restrictions on $q$? $q=2$ is always a solution – qwr Aug 19 '19 at 17:09
• @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$. – Linus Aug 20 '19 at 10:43

## 1 Answer

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

• Hey, thanks for the quick reply! This answers all my questions. :-) – Linus Aug 19 '19 at 6:55