# What is largest prime factor in Diffie-Hellman?

I was reading the paper of A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms by TAHER ELGAMAL to better understand ElGamal public-key scheme, and he stated that for any cryptosystem based on discrete logarithm problem, the prime $$p$$ should be chosen such that $$p-1$$ has at least one large prime factor.

My question is the following: how to determine if the largest prime factor of $$p-1$$ is in fact large?

## 2 Answers

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$$)
• if $$q$$ is prime
• if $$p$$ is prime
• output $$p$$ and stop.

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.

• Minor terminology note on Sophie-Germain primes - assuming both $p$ and $(p-1)/2$ are prime, then in some usages, $p$ is the Sophie-Germain prime, and in other usages, it is $(p-1)/2$ - I've heard it used both ways. Feb 4 '20 at 19:14

My question is the following: how to determine if the largest prime factor of $$p-1$$ is in fact large?

Yes, showing that $$p-1$$ is not smooth (terminology for "has a large prime factor") for random primes $$p$$ is typically difficult, and so that's not what we do.

Instead, we usually do one of these two things:

• Search for a large prime $$p$$ such that $$(p-1)/2$$ is also prime; then, we know that $$p-1$$ has a large prime factor (namely, $$(p-1)/2$$). Primes of this form are known as "safe primes"; their multiplicative group has especially nice properties.

• We pick a large prime $$q$$, and then search for a prime $$p$$ of the form $$kq + 1$$ (for some integer $$k$$ of the appropriate size). Then, we know that $$p-1$$ has a large prime factor (namely $$q$$). This can be done considerably quicker than searching for a safe prime.