How to determine if the largest prime factor of $p-1$ is in fact large?
- Most often, it is not determined from $p$ that $p-1$ has a large prime factor. Rather, a large prime factor $q$ is chosen, then it is chosen a prime $p$ of the form $p=2\,q\,r+1$ for some $r\ge1$, which insures that $p-1$ has large prime factor $q$.
- Sometime, we want $r=1$, in which case $p$ is a safe prime and $q$ the matching Sophie Germain prime. See last paragraph for how these are searched.
- For some other applications, we want $r$ large so that $p$ is much larger than $q$ (e.g. $p$ 3072-bit with $q$ 256-bit). This the Schnorr group case. For the search of $r$ making $p$ prime, when that does not hold, we typically add a small value to $r$; perhaps $1$, or a small random value in order to make $p$ more randomly seeded.
Standard generation procedures for Schnorr groups are in FIPS 186-4 appendix A.
- More rarely, it is checked after the generation of $p$ that $p-1$ has a large prime factor.
- For a safe prime, that boils down to checking that $(p-1)/2$ is prime.
- Otherwise, we could compute the small prime factors of $(p-1)/2$, multiply them (with multiplicity) to get $r$, then check if $q=(p-1)/(2\,r)$ is prime. If it does, and is suitably large, that validates $p$ (but we could fail to pull enough factors). This would only be useful for exploration or forensics: prime $q$ is typically needed to use $p$, therefore such $q$ is usually moved along $p$.
Quick search of safe primes (larger than $5$ and $7$)
Typically, we also want a certain generator $g$ (often $2$ or $3$) known to be of order $q=(p-1)/2$ (maximal prime order) or order $2\,q$ (maximal order, which is not possible for $g=3$ ). The search can be as follows:
- for each candidate $q$ (necessarily: with $q\bmod6=5$; and further with $q\bmod12=11$ for $g=2$ of order $q$, or with $q\bmod12=5$ for $g=2$ of order $2\,q$ )
- compute $p=2\,q+1$
- compute $t=g^q\bmod p$
- if $t=1$ (for $g$ of order $q$) or if $t=p-1$ (for $g$ of order $2\,q$)
The test of $t$ is a Fermat pseudoprime test. It quickly filters out most candidates $p$ that are not prime, and all primes $p$ with $g$ not of the desired order. If for some reason we do not care for a generator, it still pays to compute $t$ with $g=2$ and accept both $t=1$ or $t=p-1$.
The search can be made faster by selecting thru sieving only candidates $q$ with neither $q$ nor $2\,q+1$ divisible by a small prime.