# In which case number field sieve/index calculus is faster for solving discrete logarithm?

Given the normal discrete logarithm problem:

$$a = b^c \mod{P}$$

with prime $$P$$ and numbers $$a,b,c$$

For which kind of $$P,b$$ the NFS/IC algorithm is faster than Baby-Step/Giant-Step+ Pollard's Rho ($$\approx \mathcal{O}(\sqrt{q})$$)?

(with $$q$$ the biggest prime in factorization of $$P-1$$, with $$P$$ big prime)

Or in which cases NFS/IC it used?

Using its notation, the question is about the difficulty of the Discrete Logarithm Problem in a Schnorr Group modulo $$P$$, of prime order $$q$$. I'll assume $$b^q\bmod P=1$$ and $$b\bmod P\ne1$$.

That DLP problem is finding $$c$$ chosen at random in $$[0,q)$$ given $$P$$, $$q$$, $$b$$, and $$a$$ obtained as $$b^c\bmod P$$. Depending on parameters, the best known algorithms fall into two complexity classes:

• somewhere between $$\mathcal O(\sqrt{q}\,\ln P\,\ln\ln P)$$ [in theory] and $$\mathcal O(\sqrt{q}\,\ln^2 P)$$ for Baby-Step/Giant-Step and it's practical improvement: Pollard's Rho with distinguished points (which can be efficiently distributed and requires little memory; see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999). The cost is often stated as $$\mathcal O(\sqrt{q})$$ multiplications of integers of size $$P$$, and this has been recently shown to cost $$\mathcal O(\ln P\,\ln\ln P)$$, see this.

• something like $$\exp\left( \left(\sqrt{\frac{64}{9}} + o(1)\right)(\ln P)^{\frac{1}{3}}(\ln \ln P)^{\frac{2}{3}}\right)$$, for the Number Field Sieve applied to the Discrete Logarithm (see this).

in which cases is NFS/Index Calculus used?

For a given size of $$q$$, the first class of algorithms (Pollard's Rho..) is best for large $$P$$. The second (NFS) is faster for relatively small $$P$$, including $$q$$ a Sophie Germain prime (equivalently, $$P$$ a safe prime).

For 256‑bit $$q$$, the first class of algorithm is better for 8192-bit $$P$$, the second for 512‑bit $$P$$. I prefer not digging where exactly the crossover is, or what's the exact difference between NFS and IC.

• ty. So given the Schnorr Group $P = r \cdot q+1$ with $q$ a prime would that mean that NFS is used if the subgroup used is much smaller than $P$? In your $256$-bit-$q$ example the other factor $r$ need to be much bigger than $q$. What would be a use case of this? Wouldn't be $256$-bit safe enough? As safe as a $256$-bit EC? Mar 5 at 16:50
• @J. Doe: You are correct. With large-enough $P$, 256-bit $q$ is as safe as 256-bit ECC. In fact, Schnoor signature then DSA did just that, before ECDSA and EdDSA.
– fgrieu
Mar 5 at 16:57
• Do you have a reference or a name for the $\mathcal{O}(\sqrt{q}\ln P \ln \ln P)$ algortihm? Mar 5 at 17:13
• @fgrieu so as final conclusion (related to other question ) using a Sophie Germain 256-bit prime in normal discrete logarithm is not as safe as in EC with similar order but not a small embedding. right? Mar 5 at 18:00

The exact cost of the number field sieve algorithm is somewhat fuzzy (the usually quoted complexity is only valid in a log-asymptotic sense). Lenstra and Verheul tried to capture a more usable version of the complexity which has been broadly accepted. For parameter sets of interest the related estimates published by NIST would probably be generally agreed on:

80-bits work: 160-bit $$q$$, 1024-bit $$P$$

112-bits work: 224-bit $$q$$, 2048-bit $$P$$

128-bits work: 256-bit $$q$$, 3072-bit $$P$$

192-bits work: 384-bit $$q$$, 7680-bit $$P$$

256-bits work: 512-bit $$q$$, 15360-bit $$P$$

• Given that order at which position would be 511-bit $q$ with 512-bit $P$ or 255-bit $q$ with 256-bit $P$? Mar 5 at 22:28
• For 512-bit $P$ we can quote actual performance figures. The Logjam attack (en.wikipedia.org/wiki/Logjam_(computer_security)) was able to use the number field sieve to break such a system with a few thousand core weeks. 256-bit $P$ would be even more insecure. Mar 5 at 22:43