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?


1 Answer 1


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

  • $\begingroup$ 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) $\endgroup$
    – poncho
    Jul 31, 2017 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.