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?
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&nbsp;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.