Return to Answer

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[3]{\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.

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[3]{\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.

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: distributed Pollard's Rho with distinguished points. That's often stated as $\mathcal O(\sqrt{q})$ [which is correct if we count multiplications of integers of size $P$].

• something like $\exp\left( \left(\sqrt[3]{\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) for relatively small $P$.

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.

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[3]{\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.

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: distributed Pollard's Rho with distinguished points. That's often stated as $\mathcal O(\sqrt{q})$ [which is correct if we count multiplications of integers of size $P$].

• something like $\exp\left( \left(\sqrt[3]{\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 $q$, the first class of algorithms is best for large $P$, the second for small $P$.

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.

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: distributed Pollard's Rho with distinguished points. That's often stated as $\mathcal O(\sqrt{q})$ [which is correct if we count multiplications of integers of size $P$].

• something like $\exp\left( \left(\sqrt[3]{\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) for relatively small $P$.

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.