The Index Calculus algorithm solves the Discrete Logarithm Problem of finding $x$ with $g^x\bmod p=b$ given $g$, $b$, and prime $p$. Assume $g$ is a generator, so that $x$ is uniquely defined in $[1,p)$.

Can Index Calculus take advantage of $x$ much smaller than $p$?

If so, how low must $x$ be, and what's the saving? Is there a threshold for $x$ such that IC beast GNFS? How low must $x$ be for Baby Step / Giant Step and other algorithms with cost $\mathcal O(\sqrt x)$ modular multiplications to take back the lead?

  • $\begingroup$ No, otherwise DSA couldn't get away with subgroups much smaller than the prime. $\endgroup$ Dec 21, 2023 at 0:49
  • $\begingroup$ @Samuel Neves: I do not immediately see how we can turn an hypothetical algorithm solving the question's problem into one solving the DLP problem in a DSA/Schnorr group. The difference is that in the present problem $g$ is a generator of the whole group modulo $p$. $\endgroup$
    – fgrieu
    Dec 21, 2023 at 5:49
  • 1
    $\begingroup$ Perhaps Diffie-Hellman with short exponents would be a more direct example. The running time of, to my knowledge, all the index calculus variants is not dependent on the exponent or subgroup, only on the prime. $\endgroup$ Dec 21, 2023 at 6:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.