# Finding strong primes

Wikipedia lists the following conditions for a prime to be strong:

$p-1$ has large prime factors. That is, $p = a_1 q_1 + 1$ for some integer $a_1$ and large prime $q_1$.

$q_1-1$ has large prime factors. That is, $q_1 = a_2 q_2 + 1$ for some integer $a_2$ and large prime $q_2$.

$p+1$ has large prime factors. That is, $p = a_3 q_3 - 1$ for some integer $a_3$ and large prime $q_3$.

This seems pretty vague to me. What does "large prime" mean? How large should $p_1$ be compared to $p$?

And, most important, what is the standard way to generate large strong primes, or to check if a large prime is strong? Also, is using safe primes (of the form $p = 2*q + 1$, where $q$ is a prime) safe and/or efficient?

• How big it has to be depends on what you want to use it for. For Diffie-Hellman I'd consider 1024 bits the minimum with 2048 bits recommended. Choosing p=2*q+1 is standard practice when generating Diffie-Hellman groups. Jan 23 '15 at 17:55
• Gordon's algorithm (in Handbook of Applied Cryptography section 4.53) is a fast way to do it. The sizes can be more-or-less selected as desired (often a bit less than half the bits of p). As fgrieu says, FIPS 186-4 is a very good reference to read and use. May 11 '15 at 4:23

All the properties discussed in the question are for strong primes $p$ in the context of using $p$ as a secret factor of a large composite $n$ which factorization should be intractable; these properties are given in the landmark RSA paper (1978), without justification. Properties thought for (often public) primes used in other cryptosystems can be different.

The first property

$p-1$ has large prime factors. That is, $p = a_1 q_1 + 1$ for some integer $a_1$ and large prime $q_1$.

is intended to make factorization of $n$ using Polard's p-1 algorithm hard; this is relevant to some degree because this algorithm has a component of its cost proportional to the highest factor of $p-1$, where $p$ is the factor of $n$ exhibited by the algorithm.

Similarly, the third property

$p+1$ has large prime factors. That is, $p = a_3 q_3 - 1$ for some integer $a_3$ and large prime $q_3$.

is intended to make factorization of $n$ using Williams' p+1 algorithm hard; this is relevant to some degree because this algorithm has a component of its cost proportional to the highest factor of $p+1$, where $p$ is the factor of $n$ exhibited by the algorithm.

One standard that considers the above is FIPS 186-4 (appendix B.3), with $q_1$ and $q_3$ required to be larger than 100 bits when $p$ is 512 bits (and optionally: $q_1$ and $q_3$ larger than 140 or 170 bits when $p$ is 1024 or 1536 bits). It is hard to tell quantitatively when it makes actual sense taking precautions regarding such properties (beyond conformance to standards): it is pointless when generating a few two-factors RSA keys of at least 1024 bits; it might be useful when extremely many RSA moduli with relatively small factors (e.g. in multi-prime RSA) are generated, and an adversary would benefit finding the factorization of any modulus (rather than of a particular modulus); see this question and its answers.

The second property

$q_1-1$ has large prime factors. That is, $q_1 = a_2 q_2 + 1$ for some integer $a_2$ and large prime $q_2$.

has to do with reducing the odds that an RSA cycling attack succeeds; see this answer. I fail to find a quantitative assessment of how big $q_2$ should be, or any modern standard with this requirement. I accept the consensus that RSA cycling attacks have negligible success odds for practical key sizes (but would very much appreciate a quantitative argument!).

The standard ways to generate a large strong prime $p$ with the first and third properties (perhaps the second if required) is to choose the auxiliary primes $q_2$ (if required) then $q_1$, and $q_3$, then generate $p$; rather than choosing $p$, then trying to exhibit $q_1$ (then $q_2$ if required) and $q_3$. The later approach would be very computationally intensive: if $p$ is a random 512-bit prime, it requires the factorization of a $(p-1)/2$ and $(p+1)/2$, which are mostly random 511-bit integers, and that's typically a hard job. The former approach (used in practice) introduce significant complexity, but relatively little computational burden; several such methods are detailed in the aforementioned FIPS 186-4 appendix B.3.

• Thank you very much, this pretty much answers all my questions! Jan 24 '15 at 12:36
• @fgrieu: your answer is complete and very useful. +1 Jan 24 '15 at 16:13

According to PKCS, a strong prime p is a prime with the following properties:

• Factorisation of (p-1) contains a large prime $p_1$,
• Factorisation of (p+1) contains a large prime $p_2$.

This is equivalent to: $$p=2\times a_1 \times p_1+1=2\times a_2\times p_2-1$$ the integer $a_i$ are suffisently small compared to $p_i$. Choosing $a_i$= 1 leads to bad performance during the generation. The reason for this choice is to thwart some factorisation algorithms such as the pollard $\rho+1$ or $\rho-1$ methods. This gives a relative advantage for the Discrete Log Problem when primes are of certain forms such as Mersenne primes. But strong primes in case of RSA cryptosystem don't give any particular advantage when they are generated with the help of a true random number generator. The best factorisation algorithm know today is NFS (Number Field Sieve). Primes generation are generally based on Miller-Rabin Method. If required I could indicated how to generate strong prime.

EDIT: correction Camichael into Mersenne primes or other primes of the form $p=t^k+s$ where t , s "relatively small"

• @poncho: Sorry I've make a typo, I was thinking about primes of special form. Edited now. Jan 24 '15 at 8:29
• Are you sure of the PKCS reference? The definition of strong prime that you give is not in PKCS#1 (at least, the current version), which would seem to be the logical place. $\;$ Also, it is quite feasible to generate a prime $p$ such that $(p-1)/2$ and $(p+1)/2$ are primes (the trick is to use a sieve of width a few times $(\log p)^3$ to keep only candidates for $p$ such that any of $p$, $(p-1)/2$ and $(p+1)/2$ are divisible by small primes; then apply a probabilistic primality test).
– fgrieu
Jan 24 '15 at 12:28
• @fgrieu: take a look here emc.com/emc-plus/rsa-labs/standards-initiatives/… This is a simple explicatyive note founded in the site of EMC which acquired RSA Laboratories some years before. Using $a_i=1$ can be effective, however if you ever implemented a Prime generator, you must know that this condition is very restrictive, and for no know additional security. Sieving when relaxing for relativelly small $a_i$ is better performant. Jan 24 '15 at 13:14

p−1 has large prime factors. That is, p=a1*q1+1 for some integer a1 and large prime q1. p+1 has large prime factors. That is, p=a3*q3-1 for some integer a3 and large prime q3. as said above. To a length, if q1 and q3 are too big, there will be no primes between q1*q3 and 2^(length+1); or there are only few primes so that to be factored easily.