# DSA: How to calculate 224-bit $q$ for 2048-bit $p$

$$p$$ is a 2048 bit prime number

$$q$$ is a 224 bit prime number

I know that $$q$$ is a prime divisor of $$p-1$$, thus $$p=1 \bmod q$$ but I couldn't write efficient code to calculate this.

• I can calculate 2048 bit prime $$p$$, but how to find $$q$$ efficiently?

Currently what I am doing is generating 224-bit primes and checking whether they are dividing $$p-1$$ or not but it takes forever...

I can calculate 2048 bit prime $$p$$, but how to find $$q$$ efficiently?
Instead, you pick a 224 bit $$q$$, and then such for a 2048 bit prime of the form $$p = kq + 1$$ (for some integer $$k$$).
This can be done with essentially the same amount of effort as finding a 2048 bit prime (without constraints), and directly answers the problem, as such a $$p, q$$ pair guarantees that $$p \equiv kq + 1 \equiv 1 \pmod q$$
• @doggodonger: are you adding one to $k$, or one to $p$? Adding one to $k$ (or equivalently, adding $q$ to $p$) is the correct thing. If you add 1 to $p$, then your initial $p$ will be of the form $kq+1$; the ones after the first won't be – poncho Dec 10 '18 at 20:57