Does having the discrete logarithm of prime factors of $n$ allow us to calculate any discrete log more efficiently?

Question

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have a value of order $p_x$ for all $x$, can we calculate the discrete log efficiently?

Here the interest is in the discrete log of any base, i.e. for the general case. There may be algorithms that work well for a specific base, but here the focus should be on algorithms for all bases.

Answer 1

There are no known general-purpose algorithms that can compute the discrete logarithm efficiently with this additional information.

A special case of your question arises when $n$ is a "safe prime," i.e. a prime number such that $p=\frac{n-1}{2}$ is also prime (a Sophie-Germain prime). In this case, $\varphi(n)=2p$. Then $-1$ has order $2$, and it is very straightforward to find an element of order $p$ (pick any $g\in(\mathbb{Z}/n\mathbb{Z})^\times$ besides $1$ and $-1$, and compute $g^p$ using square-and-multiply. If $g^p=1$, then $g$ has order $p$; otherwise $g^p=-1$ and $g^2$ has order $p$). However, safe primes are often explicitly sought out as moduli for Diffie-hellman protocols precisely because there is no known attack on the discrete log problem for such $n$.

Answer 2

If you know a factor of a group order, then (probabilistically) constructing elements of that order is not too hard - just take random elements and power them by the cofactor. So the heart of the matter is whether knowing the factorization $\prod_i p_i^{k_i}$ of $\varphi(n)$ helps you to solve discrete logs in $(\mathbb{Z}/n\mathbb{Z})^\times$.

Given the factorization $\varphi(n) = \prod_i p_i^{k_i}$, the Pohlig-Hellman algorithm will solve discrete logarithms in $(\mathbb{Z}/n\mathbb{Z})^\times$ in $O(\sum_i k_i(\log n + \sqrt{p_i}))$ group operations. This is a generic group algorithm, and it is not "efficient" unless the $p_i$ are all suitably small, though it is generally an improvement over generic DLP algorithms that do not take the order factorization into account (e.g. Pollard $\rho$) unless $\varphi(n)$ is almost prime (for example, the "safe prime" case mentioned by Jonathan Love).

First, consider the case where $n$ is prime. Then, even when the $p_i$ are moderately large, Pohlig-Hellman may give no advantage over solving the discrete log in $\mathbb{F}_n^\times$ using GNFS. This is a critical point: while using subgroup structures to accelerate generic DL algorithms is classical, we still don't know how to use them to accelerate the faster DL algorithms specific to finite fields, like GNFS (and in this sense, my answer does not contradict Jonathan Love's). Either the $p_i$ are small enough to give you a speedup by switching from GNFS to Pohlig-Hellman, or you gain nothing at all from knowing the $p_i$.

This actually has a constructive cryptographic application: in some older standards for finite-field discrete-log-based crypto (for example, the old FIPS 186-4 standard for DSA signatures), you work in a prime finite field $\mathbb{F}_p$ such that

1. $p$ is large enough to resist GNFS, and
2. $\varphi(p) = p-1$ has a prime factor $q$ large enough to resist generic DLP algorithms.

The cryptosystem then operates in the order-$q$ subgroup. For example: for 128-bit security, you could take a 3072-bit prime $p$ such that $p-1$ is divisible by a 256-bit prime $q$. The advantage of doing things this way is that the protocol's exponentiations are by shorter 256-bit exponents (since they are all taken mod $q$), rather than the full-sized 3072-bit exponents you need to work in the whole of $\mathbb{F}_p^\times$ - but you don't lose any security, because the size of $q$ makes Pollard $\rho$ (and Pohlig-Hellman in $\mathbb{F}_p^\times$) too slow. There's a caveat, of course: many cryptosystems require extra work in key validation - essentially, checking that received finite field elements really are in the order-$q$ subgroup - to use this trick securely, and some cryptosystems might not be compatible with this trick at all.

The case where $n$ is not prime is much more subtle. For example, if you are in a case where you can use the factorization of $\varphi(n)$ to recover the factorization $n = \prod_i r_i^{e_i}$ faster than directly factoring $n$, then you can get a significant advantage by mapping discrete logs from $(\mathbb{Z}/n\mathbb{Z})^\times$ into the groups $(\mathbb{Z}/r_i\mathbb{Z})^\times$ and solving there. The key here is that knowing the factorization of $\varphi(n)$ lets you map the DLP into smaller multiplicative subgroups of the same ring - which, as in the prime-$n$ case above, might not be helpful - but knowing the factorization of $n$ lets you explicitly map the DLP into multiplicative groups of smaller rings, which usually is helpful.

The simplest case is when you know that $n$ is the product of two primes. Then, just knowing the value of $\varphi(n)$ - and not its factorization - lets you quickly deduce the prime factorization $n = r_1r_2$ (because in this case $r_1 + r_2 = n + 1 - \varphi(n)$, so we can recover the $r_i$ as the roots of the integer polynomial $X^2 - (n+1-\varphi(n))X + n$ using the quadratic formula). For general composite $n$, you can use the factorization of $\varphi(n)$ to factor $n$, since every odd prime $r$ dividing $n$ is necessarily in the form $m + 1$ for some even divisor $m$ of $\varphi(n)$; but if $\varphi(n)$ happens to have a large number of prime factors, then we might not find the right $m$ to help factor $n$ in polynomial time.