# What would be the most efficient way to find two large (2048bit) integers $k$ and $q$ such that $p = kq + 1$ is prime and so is $q$?

What would be the most efficient way to find two large (2048bit) integers $k$ and $q$ such that $p = kq + 1$ is prime and so is $q$?

Is there some standard algorithm that I could use?

What you ask is basically DSA parameter generation (albeit with a larger $q$). This is described in FIPS 186-4, section A.1.

Conceptually, prime generation is merely: make a random integer, see if it is prime, loop if it is not. In this case, you will want to do things the following way:

1. Generate a random integer $q$ of the intended size (2048 bits). You'll want to make sure that the top bit it set (because you want a 2048-bit integer, not a 2047-bit or less integer). You also set the bottom bit so that $q$ is odd (if it is even then it is not prime).

2. Test if $q$ is prime. If not, go back to step 1. The normal primality test is Miller-Rabin. If you use an existing big-integer library, then chances are that it already offers that test.

3. Compute the proper range for $k$. Basically, if you want the final $p$ to be exactly 4096 bits in length, then set $k_l = \lceil (2^{4095} - 1) / q \rceil$ (division of $2^{4095}-1$ by $q$, rounded up) and $k_h = \lfloor (2^{4096}-1) / q \rfloor$ (division of $2^{4096}-1$ by $q$, rounded low). You need $k$ to be such that $k_l \leq k \lt k_h$.

4. Set $s = k_h - k_l$.

5. Generate a random $r$ integer between $0$ (inclusive) and $s$ exclusive. A good way is to generate a random sequence of bits of the size of $s$ (i.e. if $s$ has length 2049 bits, generate 2049 bits); of the generate value does not fit in the range, then try again. This should ensure uniform selection in the range.

6. Compute $k = r + k_l$, then $p = kq + 1$. Thanks to how $r$ was generated, it is quaranteed that $p$ has the proper size.

7. Test whether $p$ is prime. If not, loop to step 5.

The only semi-smart thing here is that once $q$ is generated, you don't have to do it again. So it is just two successive but not nested loops, one for $q$, then another one for $k$.

In practice, finding a random prime has complexity between $O(n^3)$ and $O(n^4)$ (where $n$ is the length of the prime, in bits)(exact value depends on how well the primality test is written, in particular when it comes to avoiding the Miller-Rabin test for composites with small prime factors) so the loop on $p$ will be eight to sixteen times more expensive, on average, than the loop on $q$.

• Actually, you can do a bit better (circa a factor of 2 in my experience) by using successive values of $r$, rather than random ones. This allows you do do sieving to avoid testing values with small factors; because you use the same sieve repeatedly, you can include more small factors (which means you eliminate more composites before doing the expensive MR test) – poncho Jul 31 '17 at 19:07