9
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – poncho Feb 4 '20 at 19:14
7
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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