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

You're doing things in the wrong order.

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$$

• Thanks for the answer.Currently i am generating prime numbers with this : generate random number given n bits and test whether its prime or not with isPrime function.So how should i modify this to find p ? Am i going to multiply q some k s,(what should be k trials ??) then add 1 and check until it is prime ? I mean what should be the range of ks that i am going to test in a loop – doggodonger Dec 10 '18 at 19:37
• I guess i couldnt understand since my code still takes forever – doggodonger Dec 10 '18 at 19:56
• @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